日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺(tái) 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > php開源 > php教程 > poj1459,網(wǎng)絡(luò)流,最大流,多源點(diǎn)多匯點(diǎn)

poj1459,網(wǎng)絡(luò)流,最大流,多源點(diǎn)多匯點(diǎn)

來源:程序員人生   發(fā)布時(shí)間:2015-05-04 10:33:15 閱讀次數(shù):4823次

題意:
給幾個(gè)發(fā)電站,給幾個(gè)消耗站,再給幾個(gè)轉(zhuǎn)發(fā)點(diǎn)。
發(fā)電站只發(fā)電,消耗站只消耗電,轉(zhuǎn)發(fā)點(diǎn)只是轉(zhuǎn)發(fā)電,再給各個(gè)傳送線的傳電能力。
問你消耗站能取得的最多電是多少。

思路:增加1個(gè)超級(jí)源點(diǎn),和超級(jí)匯點(diǎn)。。把所給的發(fā)電站都和超級(jí)源點(diǎn)相連,把所給的消耗戰(zhàn)都和超級(jí)匯點(diǎn)相連。。用EK求最大流。


模板有幾個(gè)地方要注意。

1:start是編號(hào)最前的點(diǎn),last是編號(hào)最后的點(diǎn)

模板默許last是m,根據(jù)需要要把m都改成編號(hào)最后的點(diǎn)的號(hào)碼

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> #include<queue> #include<stdlib.h> #define inf 0x3f3f3f3f using namespace std; int map[1000][1000], path[1000], flow[1000], n, m,nc,np,start; int last; queue<int>que; int bfs() { int i, t; while (que.size())que.pop(); memset(path, ⑴, sizeof(path)); path[start] = 0; flow[start] = inf; que.push(start); while (que.size()) { int t = que.front(); que.pop(); if (t == last) break; for (i = 0; i <= n+1; i++) { if (i != start && path[i] == ⑴ && map[t][i]) { flow[i] = min(flow[t], map[t][i]); path[i] = t; que.push(i); } } } if (path[last] == ⑴)return ⑴; else return flow[n+1]; } int liu() { int maxflow = 0, temp, now, pre; while ((temp = bfs()) != ⑴) { maxflow += temp; now = last; while (now != start) { pre = path[now]; map[pre][now] -= temp; map[now][pre] += temp; now = pre; } } return maxflow; } char temp[20]; int main() { int i, j, k, from, to, cost,u,v,z; while (~scanf("%d%d%d%d", &n,&np,&nc,&m)) { memset(map, 0, sizeof(map)); for (i = 0; i < m; i++) { scanf("%s", temp); sscanf(temp, "(%d,%d)%d", &u, &v, &z); map[u+1][v+1] += z; } for (i = 0; i < np; i++) { scanf("%s", temp); sscanf(temp, "(%d)%d", &u, &z); map[0][u+ 1] += z; } for (i = 0; i < nc; i++) { scanf("%s", temp); sscanf(temp, "(%d)%d", &u, &z); map[u+1][n+1] += z; } last=n + 1; start = 0; cout << liu() << endl; } }


生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 午夜精品视频 | 国产二区久久 | 国产一区二区三区欧美 | 亚洲精品大全 | 在线观看精品一区 | 欧美日韩一区二区三区不卡 | 日本性网站 | 成年人视频免费在线观看 | 亚洲欧美婷婷 | 99成人免费视频 | 日韩国产欧美一区 | 国产成人a亚洲精品 | 精品久久中文字幕 | 一区二区成人在线 | 最新免费av网站 | av免费播放 | 在线播放国产一区二区三区 | 日本在线不卡一区 | 精品久久久国产 | 欧美日韩一区在线 | 久久黄视频 | 国产精品成人一区二区三区 | 久久久久久久久网站 | 国产精品久久久久久久久久久久久久 | 亚洲国产精品一区二区久久 | 亚洲一区中文字幕 | 午夜激情视频在线观看 | 一个人看的www日本高清视频 | 欧美精品一区视频 | 国产露脸女上位在线视频 | 欧美在线国产 | 精品一区二区三区四区 | 久久wwww| 99re视频在线观看 | 久久三级视频 | 精品不卡 | 免费国产在线观看 | 亚洲精品成人在线播放 | 亚洲成人精品在线观看 | 蜜臀麻豆| 日韩欧美一卡二卡 |