關鍵在建圖，轉換器連一條容量無限的邊表示可以轉化無數次，設備的插頭連源點，插座連匯點。

dinic手敲已熟練，輸出格式又被坑，總結一下，輸出空行多case的，一個換行是必要的，最后一個不加空行，有Testcase最后一個不要換行，沒有testcase最后一個要加換行，想起那天gold miner PE了兩發。

對dinic網絡流的簡單理解：bfs找有沒有增廣路，dfs增廣。

關鍵的概念：反向邊，給一個反悔的機會。

#include<bits/stdc++.h> using namespace std; int n,m; map<string,int> mp; map<string,int>::iterator it; #define MP make_pair #define PB push_back #define fi first #define se secondint id_cnt;int ID(const string &s) {if((it=mp.find(s))!=mp.end()) return it->se;mp.insert(MP(s,id_cnt));return id_cnt++; }const int maxn = 404, INF = 0x3f3f3f3f; int S,T; struct Edge {int v,nxt,cap,flow; }edges[maxn<<1];int head[maxn],cur[maxn],ecnt;void addEdge(int u,int v,int c) {edges[ecnt].nxt = head[u];edges[ecnt].cap = c;edges[ecnt].flow = 0;edges[ecnt].v = v;head[u] = ecnt++; }void AddEdge(int u,int v,int c) {addEdge(u,v,c);addEdge(v,u,0); }int d[maxn]; bool vis[maxn]; bool bfs() {memset(vis,0,sizeof(bool)*id_cnt);queue<int> q;q.push(S);d[S] = 0; vis[S] = true;while(q.size()){int u = q.front(); q.pop();for(int i = head[u]; ~i; i = edges[i].nxt){Edge &e = edges[i];if(!vis[e.v] && e.cap>e.flow){vis[e.v] = true;d[e.v] = d[u]+1;q.push(e.v);}}}return vis[T]; }int dfs(int u,int a) {if(u == T||!a) return a;int flow = 0,f;for(int &i = cur[u]; ~i; i = edges[i].nxt){Edge &e = edges[i];if(d[e.v] == d[u]+1 && (f = dfs(e.v,min(a,e.cap-e.flow))>0)){e.flow += f;edges[i^1].flow -= f;flow += f;a -= f;if(!a) break;}}return flow; }int MaxFlow() {int ret = 0;while(bfs()){memcpy(cur,head,sizeof(int)*id_cnt);ret += dfs(S,INF);}return ret; }void init() {memset(head,-1,sizeof(head));mp.clear(); id_cnt = 2;ecnt = 0; }int main() {//freopen("in.txt","r",stdin);char str1[42],str2[42];int Testcase; scanf("%d",&Testcase);S = 0; T = 1;while(Testcase--){int n,m,k;init();scanf("%d",&n);for(int i = 0; i < n; i++){scanf("%s",str1);AddEdge(ID(str1),T,1);}scanf("%d",&m);for(int i = 0; i < m; i++){scanf("%s%s",str1,str2);AddEdge(S,ID(str2),1);}scanf("%d",&k);for(int i = 0; i < k; i++){scanf("%s%s",str1,str2);AddEdge(ID(str1),ID(str2),INF);}int ans = m-MaxFlow();printf("%d\n",ans);if(Testcase)putchar('\n');}return 0; }

?

轉載于:https://www.cnblogs.com/jerryRey/p/4759107.html

總結

以上是生活随笔為你收集整理的UVA 753 A Plug for UNIX （最大流）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。