首页 > 代码库 > Uvaoj 11248 Frequency Hopping(Dinic求最小割)
Uvaoj 11248 Frequency Hopping(Dinic求最小割)
题意：1到n节点（节点之间有一定的容量），需要流过C的流量，问是否可以？如果可以输出possible， 否则如果可以扩大任意一条边的容量
可以达到目的，那么输出possible option：接着输出每一条可以达到目的的边（按升序），再否则输出not possible
思路：先求一次最大流，如果流量至少为C，则直接输出possible，否则需要修改的弧一定在最小割里！
接着吧这些弧（最小割里的）的容量设为无穷大，然后在求最大流，看最大流的流量能否满足是C即可，如果满足了，那就把这一条边记录下来
分析：最大流的程序没有必要完全的执行完毕，知道当前的流量>=C那么就可以中止最大流的程序！
还有就是第一次的最大流程序如果没有找到>=C的最大流，那么此时的流量留着，下一次在最小割里扩容的时候，总是接着第一次Dinic的流量
继续寻找....
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 #define N 105 8 #define INF 2000000005 9 using namespace std; 10 11 struct EDGE{ 12 int u, v, nt, cap; 13 bool flag; 14 bool vis; 15 EDGE(){} 16 EDGE(int u, int v, int nt, int cap, bool flag):u(u), v(v), nt(nt), cap(cap), flag(flag){} 17 }; 18 19 struct node{ 20 int x, y; 21 node(){} 22 node(int x, int y) : x(x), y(y){} 23 }; 24 25 int pos[10005]; 26 27 node ans[10005]; 28 int preCost[20005]; 29 int vis[20005]; 30 int p[20005]; 31 int pcnt; 32 int cnt; 33 34 vector<EDGE>g; 35 int first[N]; 36 37 int d[N]; 38 int n, e, c; 39 40 void addEdge(int u, int v, int c){ 41 g.push_back(EDGE(u, v, first[u], c, true)); 42 first[u] = g.size() - 1; 43 g.push_back(EDGE(v, u, first[v], 0, false)); 44 first[v] = g.size() - 1; 45 } 46 47 bool bfs(){ 48 memset(d, 0, sizeof(d)); 49 d[1] = 1; 50 queue<int>q; 51 q.push(1); 52 while(!q.empty()){ 53 int u = q.front(); 54 q.pop(); 55 for(int i = first[u]; ~i; i = g[i].nt){ 56 int v = g[i].v; 57 if(!d[v] && g[i].cap > 0){ 58 d[v] = d[u] + 1; 59 q.push(v); 60 } 61 } 62 } 63 if(d[n] == 0) return false; 64 return true; 65 } 66 67 bool cmp(node a, node b){ 68 if(a.x == b.x) 69 return a.y < b.y; 70 return a.x < b.x; 71 } 72 73 int leave; 74 75 int dfs(int u, int totf){ 76 int flow = 0; 77 if(u ==n || totf==0) return totf; 78 for(int i = first[u]; ~i; i = g[i].nt){ 79 int v = g[i].v; 80 if(d[v] == d[u] + 1 && g[i].cap > 0){ 81 int ff = dfs(v, min(totf-flow, g[i].cap)); 82 if(ff > 0){ 83 if(!vis[i]){ 84 p[pcnt++]=i; 85 preCost[i] = g[i].cap; 86 vis[i] = 1; 87 } 88 g[i].cap -= ff; 89 90 if(!vis[i^1]){ 91 p[pcnt++]=i^1; 92 preCost[i^1] = g[i^1].cap; 93 vis[i^1] = 1; 94 } 95 g[i^1].cap += ff; 96 flow += ff; 97 98 if(flow >= leave){ 99 flow = leave;100 return flow;101 }102 103 if(totf == flow) break;104 }105 else d[v] = -1;106 }107 }108 return flow;109 }110 111 bool Dinic(){112 leave = c;113 while(bfs()){114 leave -= dfs(1, INF);115 if(leave == 0) break;116 }117 if(leave == 0) return true;118 return false;119 }120 121 122 123 int main(){124 int cas = 0;125 while(scanf("%d%d%d", &n, &e, &c)){126 if(!n) break;127 memset(first, -1, sizeof(first));128 g.clear();129 cnt = 0;130 while(e--){131 int x, y, z;132 scanf("%d%d%d", &x, &y, &z);133 addEdge(x, y, z);134 }135 printf("Case %d: ", ++cas);//这一块差点没有把我气死...居然有一个空格，没有看清楚啊...一直PE.136 137 if(n==1){138 printf("possible\n");139 continue;140 }141 142 if(Dinic()) printf("possible\n");143 else{144 int len = g.size();145 for(int i=0; i<len; ++i)146 if(g[i].cap == 0 && g[i].flag)147 pos[cnt++] = i;//得到最小割148 int cc = leave;//第一次Dinic之后，还剩下多少的流量需要流过149 int ret = 0;150 for(int i=0; i<cnt; ++i){151 c = cc;//新的需要流过的流量152 pcnt = 0;153 g[pos[i]].cap = INF;154 memset(vis, 0, sizeof(vis));155 if(Dinic())//如果增广成功，那么这条最小割满足156 ans[ret++] = node(g[pos[i]].u, g[pos[i]].v);157 for(int j=0; j<pcnt; ++j)158 g[p[j]].cap = preCost[p[j]];//将Dinic中所经过的边的值恢复成第一次Dinic之后的值！159 g[pos[i]].cap = 0;160 }161 if( ret > 0 ){162 sort(ans, ans+ret, cmp);163 printf("possible option:(%d,%d)", ans[0].x, ans[0].y);164 for(int i=1; i<ret; ++i)165 printf(",(%d,%d)", ans[i].x, ans[i].y);166 printf("\n");167 }168 else printf("not possible\n");169 }170 } 171 return 0;172 }
Uvaoj 11248 Frequency Hopping(Dinic求最小割)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。