1163: [Baltic2008]Mafia
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 123 Solved: 70[][][]Description
匪徒准备从一个车站转移毒品到另一个车站,警方准备进行布控. 对于每个车站进行布控都需要一定的代价,现在警方希望使用最小的代价控制一些车站,使得去掉这些车站后，匪徒无法从原定的初始点到达目标点
Input
第一行输入N,M代表车站的总个数,及有多少条双向边连接它们. 2<=n<=200 , 1 <=m<=20000. 第二行给出两个数a,b,代表匪徒的出发点及目标点.1<=a,b<=N,a<>b. 再下来有N行,给出对第i个车站进行布控所需要的Money,其不超过10 000 000 再下来M行,用于描述图的结构.
Output
最少需要多少Money
Sample Input
5 6 5 3 2 4 8 3 10 1 5 1 2 2 4 4 5 2 3 3 4
Sample Output
5
HINT
Source
[][][]
题解：
本题是一道明显的最小割问题，最大流最小割模板一定要掌握，剩下的就是建图了，此题建图有很多细节，需要反复理解题意，并结合现实情况，我做这题一直WA了两天，一直看模板，，，但最后发现是建图错了!!! 下面是我认为比较重要的细节：
1.裂点限流，对于一个车站裂成两个点，我称之为“入点”和“出点”，连接一条“入点”到“出点”的有向边，注意，是“有向边”，只有切断这个边，才算控制了此车站。
然后假设是车站x和车站y，使x的“出点”连向y的“入点”，再使y的“出点”连向x的“入点”，边权设inf
2.起点S是S的“入点”，因为罪犯就在S点，警察的任务是切断转移，抄老窝也算一种方法啊。
3.终点T是T的“出点”，因为警察可以控制终点来切断路线。。。。我就是在这错了两天的！！！我一直认为要把罪犯控制在终点之内，，这是错的！！！！
4.边的条数<=2w,可不要认为数组开到4w就够了，因为还有裂点之间的边啊。。。o(╯□╰)o就因为这RE了好多次。。。。
给出两种构图方式，个人认为第一种简单：
1 #include2 using namespace std; 3 typedef long long LL; 4 const LL inf=0x3f3f3f3f; 5 const LL maxn=600; 6 const LL maxm=100000; 7 struct Edge{ 8 LL to;//这条边通向的点 9 LL rest;//这条变的权值 10 LL next;//与这条边相连的上一条边 11 };12 Edge edge[maxn];//edge[i]代表一条有向边 13 LL head[maxm];14 LL ecnt=1;15 inline void AddEdge(LL x,LL y,LL r){16 edge[++ecnt].to=y; edge[ecnt].rest=r; edge[ecnt].next=head[x]; head[x]=ecnt;17 edge[++ecnt].to=x; edge[ecnt].rest=0; edge[ecnt].next=head[y]; head[y]=ecnt;18 }19 LL N,M,S,T;20 LL dis[maxn];21 22 inline bool BFS(){23 memset(dis,0,sizeof(dis));24 dis[S]=1;25 static queue Q;26 while(Q.size()>0) Q.pop();27 Q.push(S);28 while(Q.size()>0){29 LL x=Q.front(); Q.pop();30 for(LL e=head[x] ; e ; e=edge[e].next){ //e表示的是边，不是点 31 LL d=edge[e].to;32 if(edge[e].rest&&dis[d]==0){ //边权不为零且这条边通向的点的 33 dis[d]=dis[x]+1;34 Q.push(d);35 if(d==T) return true;36 }37 }38 }39 return false;40 }41 42 inline LL DFS(LL x,LL flow){43 if(x==T) return flow;44 LL now=0,tmp;45 for(LL e=head[x]; e ;e=edge[e].next){46 if(edge[e].rest&&dis[edge[e].to]==dis[x]+1){47 tmp=DFS(edge[e].to,min(flow-now,edge[e].rest));48 edge[e].rest-=tmp; 49 edge[e ^ 1].rest+=tmp;50 now+=tmp;51 if(now==flow) return now;52 }53 }54 return now;55 }56 inline LL dinic(){57 LL ans=0;58 while(BFS()){59 ans+=DFS(S,inf);60 }61 return ans;62 }63 LL money[maxn];64 LL tot;65 int main(){66 cin>>N>>M;67 cin>>S>>T;68 T+=N;69 for(LL i=1;i<=N;i++){70 LL v;71 cin>>v;72 AddEdge(i,i+N,v);73 }74 for(LL i=1;i<=M;i++){75 LL u,v;76 cin>>u>>v;77 AddEdge(u+N,v,inf);78 AddEdge(v+N,u,inf);79 }80 cout<
第二种：
1 #include2 using namespace std; 3 typedef long long LL; 4 const LL inf=0x3f3f3f3f; 5 const LL maxn=600; 6 const LL maxm=100000; 7 struct Edge{ 8 LL to;//这条边通向的点 9 LL rest;//这条变的权值 10 LL next;//与这条边相连的上一条边 11 };12 Edge edge[maxm];//edge[i]代表一条有向边 13 LL head[maxm];14 LL ecnt=1;15 inline void AddEdge(LL x,LL y,LL r){16 edge[++ecnt].to=y; edge[ecnt].rest=r; edge[ecnt].next=head[x]; head[x]=ecnt;17 edge[++ecnt].to=x; edge[ecnt].rest=0; edge[ecnt].next=head[y]; head[y]=ecnt;18 }19 LL N,M,S,T;20 LL dis[maxn];21 22 inline bool BFS(){23 memset(dis,0,sizeof(dis));24 dis[S]=1;25 static queue Q;26 while(Q.size()>0) Q.pop();27 Q.push(S);28 while(Q.size()>0){29 LL x=Q.front(); Q.pop();30 for(LL e=head[x] ; e ; e=edge[e].next){ //e表示的是边，不是点 31 LL d=edge[e].to;32 if(edge[e].rest&&dis[d]==0){ //边权不为零且这条边通向的点的 33 dis[d]=dis[x]+1;34 Q.push(d);35 if(d==T) return true;36 }37 }38 }39 return false;40 }41 42 inline LL DFS(LL x,LL flow){43 if(x==T) return flow;44 LL now=0,tmp;45 for(LL e=head[x]; e ;e=edge[e].next){46 if(edge[e].rest&&dis[edge[e].to]==dis[x]+1){47 tmp=DFS(edge[e].to,min(flow-now,edge[e].rest));48 edge[e].rest-=tmp; 49 edge[e ^ 1].rest+=tmp;50 now+=tmp;51 if(now==flow) return now;52 }53 }54 return now;55 }56 inline LL dinic(){57 LL ans=0;58 while(BFS()){59 ans+=DFS(S,inf);60 }61 return ans;62 }63 LL money[maxn];64 LL tot;65 int main(){66 cin>>N>>M;67 cin>>S>>T;68 for(LL i=1;i<=N;i++) scanf("%d",&money[i]);69 for(LL i=1;i<=N;i++){70 tot++;71 AddEdge(tot,tot+1,money[i]);72 tot++;73 }74 for(LL i=1;i<=M;i++){75 LL r,l;76 cin>>r>>l;77 LL rr,ll; 78 rr=(r-1)*2+2;//出点 79 ll=(l-1)*2+1;//入点 80 AddEdge(rr,ll,inf);81 ll++;82 rr--;83 AddEdge(ll,rr,inf);84 }85 S=(S-1)*2+1;86 T=(T-1)*2+2;87 cout<