腾讯云 wordpress 主题,电商seo是什么,企业标志logo设计免费,seo主要做哪些工作题意#xff1a;1到n节点#xff08;节点之间有一定的容量#xff09;#xff0c;需要流过C的流量#xff0c;问是否可以#xff1f;如果可以输出possible#xff0c; 否则如果可以扩大任意一条边的容量 可以达到目的#xff0c;那么输出possible option#xff1a;接… 题意1到n节点节点之间有一定的容量需要流过C的流量问是否可以如果可以输出possible 否则如果可以扩大任意一条边的容量 可以达到目的那么输出possible option接着输出每一条可以达到目的的边按升序再否则输出not possible 思路先求一次最大流如果流量至少为C则直接输出possible否则需要修改的弧一定在最小割里 接着吧这些弧最小割里的的容量设为无穷大然后在求最大流看最大流的流量能否满足是C即可如果满足了那就把这一条边记录下来 分析最大流的程序没有必要完全的执行完毕知道当前的流量C那么就可以中止最大流的程序 还有就是第一次的最大流程序如果没有找到C的最大流那么此时的流量留着下一次在最小割里扩容的时候总是接着第一次Dinic的流量 继续寻找.... 1 #includeiostream2 #includecstring3 #includecstdio4 #includealgorithm5 #includevector6 #includequeue7 #define N 1058 #define INF 20000000059 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 vectorEDGEg;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 queueintq;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 || totf0) 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(n1){
138 printf(possible\n);
139 continue;
140 }
141
142 if(Dinic()) printf(possible\n);
143 else{
144 int len g.size();
145 for(int i0; ilen; 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 i0; icnt; 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 j0; jpcnt; 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, ansret, cmp);
163 printf(possible option:(%d,%d), ans[0].x, ans[0].y);
164 for(int i1; iret; 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 } View Code 转载于:https://www.cnblogs.com/hujunzheng/p/4014923.html
