学步园

//这个题做的蛋疼,,,自己的想法就是不对,归根结底还是对最大流这种基本的东西不熟悉,,它的内涵都不懂,自己真是水呀

//我第一想的办法是把regulator[]当做限制,WA,原因没分析到,这是WA代码

#include <iostream><br /> #include <cstdio><br /> #include <queue><br /> #include <memory.h></p> <p>using namespace std;<br /> const int MAX=105,INF=1<<30;<br /> int regulator[MAX],m,cap[MAX][MAX],flow[MAX][MAX],<br /> startN,sink,t,a[MAX],n,p[MAX];<br /> queue<int> q;<br /> int smallest(int i,int j,int k){<br /> int s=i<j?i:j;<br /> return s<k?s:k;<br /> }<br /> int maxFlow(){<br /> memset(flow,0,sizeof(flow));<br /> int f=0,u;<br /> while(1){<br /> memset(a,0,sizeof(a));//a代表指向结点[v]的增广路<br /> a[0]=INF;<br /> q.push(0);<br /> //cout<<"s: "<<endl;<br /> while(!q.empty()){<br /> u=q.front(); q.pop();<br /> //cout<<u<<" "<<a[u]<<endl;<br /> for(int v=1;v<=n;v++){<br /> if(!a[v]&&cap[u][v]>flow[u][v]&&<br /> regulator[v]>flow[u][v]){<br /> p[v]=u; q.push(v);<br /> //if(v==1)<br /> // cout<<"ssssssssss: "<<u<br /> // <<" "<<flow[u][v]<<endl;<br /> a[v]=smallest(a[u],cap[u][v]-flow[u][v],<br /> regulator[v]);<br /> //regulator[v]-=a[v];<br /> }<br /> }<br /> }<br /> if(!a[t])<br /> break;<br /> //cout<<a[t]<<endl;<br /> for(u=t;u!=0;u=p[u]){<br /> flow[p[u]][u]+=a[t];//从汇点开始更新正向流<br /> flow[u][p[u]]-=a[t];//从汇点开始更新反向流<br /> //regulator[u]-=a[t];//从汇点开始更新regulator<br /> }<br /> f+=a[t];<br /> }<br /> return f;<br /> }<br /> int main()<br /> {<br /> freopen("i.txt","r",stdin);<br /> int v1,v2,w;<br /> regulator[0]=INF;<br /> while(cin>>n){<br /> memset(cap,0,sizeof(cap));<br /> for(int i=1;i<=n;i++)<br /> cin>>regulator[i];<br /> cin>>m;<br /> for(int i=0;i<m;i++){<br /> cin>>v1>>v2>>w;<br /> cap[v1][v2]=w;<br /> }<br /> cin>>startN>>sink;<br /> //cout<<startN<<" "<<sink<<endl;<br /> for(int i=0;i<startN;i++){<br /> cin>>v1;<br /> //cout<<v1<<endl;<br /> cap[0][v1]=INF;<br /> }</p> <p> t=++n;<br /> regulator[t]=INF;<br /> for(int i=0;i<sink;i++){<br /> cin>>v1;<br /> cap[v1][t]=regulator[v1];<br /> }<br /> cout<<maxFlow()<<endl;<br /> }<br /> return 0;<br /> }</p> <p>

//然后我又想到了一个优化 就是两个点之间的容量cap只能是它u,v,的regulator 和他们边的cap的最小值,,结果居然水过去了,代码如下

#include <iostream><br /> #include <cstdio><br /> #include <queue><br /> #include <memory.h></p> <p>using namespace std;<br /> const int MAX=105,INF=1<<30;<br /> int regulator[MAX],m,cap[MAX][MAX],flow[MAX][MAX],<br /> startN,sink,t,a[MAX],n,p[MAX];<br /> queue<int> q;<br /> int smallest(int i,int j,int k){<br /> int s=i<j?i:j;<br /> return s<k?s:k;<br /> }<br /> int maxFlow(){<br /> memset(flow,0,sizeof(flow));<br /> int f=0,u;<br /> while(1){<br /> memset(a,0,sizeof(a));//a代表指向结点[v]的增广路<br /> a[0]=INF;<br /> q.push(0);<br /> while(!q.empty()){<br /> u=q.front(); q.pop();<br /> for(int v=1;v<=n;v++){<br /> if(!a[v]&&cap[u][v]>flow[u][v]){<br /> p[v]=u; q.push(v);<br /> a[v]=a[u]<cap[u][v]-flow[u][v]?<br /> a[u]:cap[u][v]-flow[u][v];<br /> //regulator[v]-=a[v];<br /> }<br /> }<br /> }<br /> if(!a[t])<br /> break;<br /> //cout<<a[t]<<endl;<br /> for(u=t;u!=0;u=p[u]){<br /> flow[p[u]][u]+=a[t];//从汇点开始更新正向流<br /> flow[u][p[u]]-=a[t];//从汇点开始更新反向流<br /> //regulator[u]-=a[t];//从汇点开始更新regulator<br /> }<br /> f+=a[t];<br /> }<br /> return f;<br /> }<br /> int main()<br /> {<br /> freopen("i.txt","r",stdin);<br /> int v1,v2,w;<br /> regulator[0]=INF;<br /> while(cin>>n){<br /> memset(cap,0,sizeof(cap));<br /> for(int i=1;i<=n;i++)<br /> cin>>regulator[i];<br /> cin>>m;<br /> for(int i=0;i<m;i++){<br /> cin>>v1>>v2>>w;<br /> cap[v1][v2]=smallest(w,regulator[v1],regulator[v2]);<br /> }<br /> cin>>startN>>sink;<br /> //cout<<startN<<" "<<sink<<endl;<br /> for(int i=0;i<startN;i++){<br /> cin>>v1;<br /> //cout<<v1<<endl;<br /> cap[0][v1]=regulator[v1];<br /> }</p> <p> t=++n;<br /> regulator[t]=INF;<br /> for(int i=0;i<sink;i++){<br /> cin>>v1;<br /> cap[v1][t]=regulator[v1];<br /> }<br /> cout<<maxFlow()<<endl;<br /> }<br /> return 0;<br /> }</p> <p>

//最后才是对的做法,,就是拆点,,其实我第一个思路就是这个,只是当时觉得麻烦没写,其实一点都不麻烦

#include <iostream><br /> #include <cstdio><br /> #include <queue><br /> #include <memory.h></p> <p>using namespace std;<br /> const int MAX=105*2,INF=1<<30;<br /> int regulator[MAX],m,cap[MAX][MAX],flow[MAX][MAX],<br /> startN,sink,t,a[MAX],n,p[MAX],<br /> head[MAX],rear[MAX],dian;<br /> queue<int> q;</p> <p>int maxFlow(){<br /> memset(flow,0,sizeof(flow));<br /> int f=0,u;<br /> while(1){<br /> memset(a,0,sizeof(a));//a代表指向结点[v]的增广路<br /> a[0]=INF;<br /> q.push(0);<br /> while(!q.empty()){<br /> u=q.front(); q.pop();<br /> for(int v=1;v<=n;v++){<br /> if(!a[v]&&cap[u][v]>flow[u][v]){<br /> p[v]=u; q.push(v);<br /> a[v]=a[u]<cap[u][v]-flow[u][v]?<br /> a[u]:cap[u][v]-flow[u][v];<br /> //regulator[v]-=a[v];<br /> }<br /> }<br /> }<br /> if(!a[t])<br /> break;<br /> //cout<<a[t]<<endl;<br /> for(u=t;u!=0;u=p[u]){<br /> flow[p[u]][u]+=a[t];//从汇点开始更新正向流<br /> flow[u][p[u]]-=a[t];//从汇点开始更新反向流<br /> //regulator[u]-=a[t];//从汇点开始更新regulator<br /> }<br /> f+=a[t];<br /> }<br /> return f;<br /> }<br /> int main()<br /> {<br /> freopen("i.txt","r",stdin);<br /> int v1,v2,w;<br /> regulator[0]=INF;<br /> while(cin>>n){<br /> dian=1;<br /> memset(cap,0,sizeof(cap));<br /> for(int i=1;i<=n;i++){<br /> cin>>regulator[i];<br /> head[i]=dian; rear[i]=dian+1;<br /> cap[dian][dian+1]=regulator[i];<br /> dian+=2;<br /> }<br /> cin>>m;<br /> for(int i=0;i<m;i++){<br /> cin>>v1>>v2>>w;<br /> cap[rear[v1]][head[v2]]=w;<br /> }<br /> cin>>startN>>sink;<br /> //cout<<startN<<" "<<sink<<endl;<br /> for(int i=0;i<startN;i++){<br /> cin>>v1;<br /> //cap[0][v1]=regulator[v1];<br /> cap[0][head[v1]]=INF;<br /> }<br /> //t=++n;<br /> t=n=dian;<br /> //regulator[t]=INF;<br /> for(int i=0;i<sink;i++){<br /> cin>>v1;<br /> //cout<<v1<<endl;<br /> cap[rear[v1]][t]=INF;<br /> }<br /> /*for(int i=1;i<=n;i++){<br /> for(int j=1;j<=n;j++){<br /> cout<<cap[i][j]<<" ";<br /> }<br /> cout<<endl;<br /> }*/<br /> cout<<maxFlow()<<endl;<br /> }<br /> return 0;<br /> }</p> <p>

//为什么我第2种方法是错的,第3种是对的呢?,可以看一下数据

3<br /> 100 50 25<br /> 3<br /> 1 2 100<br /> 2 3 100<br /> 1 3 100<br /> 1 2<br /> 1 2 3<br /> 3<br /> 100 20 30<br /> 2<br /> 2 1 100<br /> 3 1 100<br /> 3 1<br /> 1 2 3 1</p> <p>8<br /> 20 15 17 5 10 25 20 50<br /> 10<br /> 1 4 15<br /> 1 5 5<br /> 2 5 10<br /> 2 6 10<br /> 3 6 25<br /> 6 5 10<br /> 4 7 10<br /> 5 7 15<br /> 5 8 10<br /> 6 8 15<br /> 3 2<br /> 1 2 3 7 8<br /> 5<br /> 20 15 10 20 20<br /> 4<br /> 1 3 5<br /> 2 3 10<br /> 3 4 10<br /> 3 5 10<br /> 2 2<br /> 1 2 4 5</p> <p>

//如果你仔细分析最后一个数据的结点5,你会发现第2种方法忽略了结点5的regulator是10的限制而让5结点流出了 15的流量