1163: [Baltic2008]Mafia

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 123 Solved: 70
[Submit][Status][Discuss]

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

HINT

Source

　　　　　　　　　　　　　　　　　　　　　　[Submit][Status][Discuss]

题解：

　　本题是一道明显的最小割问题，最大流最小割模板一定要掌握，剩下的就是建图了，此题建图有很多细节，需要反复理解题意，并结合现实情况，我做这题一直WA了两天，一直看模板，，，但最后发现是建图错了!!! 下面是我认为比较重要的细节：

　 1.裂点限流，对于一个车站裂成两个点，我称之为“入点”和“出点”，连接一条“入点”到“出点”的有向边，注意，是“有向边”，只有切断这个边，才算控制了此车站。

　　然后假设是车站x和车站y，使x的“出点”连向y的“入点”，再使y的“出点”连向x的“入点”，边权设inf

　　2.起点S是S的“入点”，因为罪犯就在S点，警察的任务是切断转移，抄老窝也算一种方法啊。

　　3.终点T是T的“出点”，因为警察可以控制终点来切断路线。。。。我就是在这错了两天的！！！我一直认为要把罪犯控制在终点之内，，这是错的！！！！

　　4.边的条数<=2w,可不要认为数组开到4w就够了，因为还有裂点之间的边啊。。。o(╯□╰)o就因为这RE了好多次。。。。

　　给出两种构图方式，个人认为第一种简单：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const LL inf=0x3f3f3f3f;

 const LL maxn=;

 const LL maxm=;

 struct Edge{

     LL to;//这条边通向的点

     LL rest;//这条变的权值

     LL next;//与这条边相连的上一条边

 };

 Edge edge[maxn];//edge[i]代表一条有向边

 LL head[maxm];

 LL ecnt=;

 inline void AddEdge(LL x,LL y,LL r){

     edge[++ecnt].to=y; edge[ecnt].rest=r; edge[ecnt].next=head[x]; head[x]=ecnt;

     edge[++ecnt].to=x; edge[ecnt].rest=; edge[ecnt].next=head[y]; head[y]=ecnt;

 }

 LL N,M,S,T;

 LL dis[maxn];

 inline bool BFS(){

     memset(dis,,sizeof(dis));

     dis[S]=;

     static queue<LL> Q;

     while(Q.size()>) Q.pop();

     Q.push(S);

     while(Q.size()>){

         LL x=Q.front(); Q.pop();

         for(LL e=head[x] ; e ; e=edge[e].next){//e表示的是边，不是点

             LL d=edge[e].to;

             if(edge[e].rest&&dis[d]==){//边权不为零且这条边通向的点的

                 dis[d]=dis[x]+;

                 Q.push(d);

                 if(d==T) return true;

             }

         }

     }

     return false;

 }

 inline LL DFS(LL x,LL flow){

     if(x==T) return flow;

     LL now=,tmp;

     for(LL e=head[x]; e ;e=edge[e].next){

         if(edge[e].rest&&dis[edge[e].to]==dis[x]+){

             tmp=DFS(edge[e].to,min(flow-now,edge[e].rest));

             edge[e].rest-=tmp;

             edge[e ^ ].rest+=tmp;

             now+=tmp;

             if(now==flow) return now;

         }

     }

     return now;

 }

 inline LL dinic(){

     LL ans=;

     while(BFS()){

         ans+=DFS(S,inf);

     }

     return ans;

 }

 LL money[maxn];

 LL tot;

 int main(){

     cin>>N>>M;

     cin>>S>>T;

     T+=N;

     for(LL i=;i<=N;i++){

         LL v;

         cin>>v;

         AddEdge(i,i+N,v);

     }

     for(LL i=;i<=M;i++){

         LL u,v;

         cin>>u>>v;

         AddEdge(u+N,v,inf);

         AddEdge(v+N,u,inf);

     }

     cout<<dinic();

     return ;

 }

　　第二种：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const LL inf=0x3f3f3f3f;

 const LL maxn=;

 const LL maxm=;

 struct Edge{

     LL to;//这条边通向的点

     LL rest;//这条变的权值

     LL next;//与这条边相连的上一条边

 };

 Edge edge[maxm];//edge[i]代表一条有向边

 LL head[maxm];

 LL ecnt=;

 inline void AddEdge(LL x,LL y,LL r){

     edge[++ecnt].to=y; edge[ecnt].rest=r; edge[ecnt].next=head[x]; head[x]=ecnt;

     edge[++ecnt].to=x; edge[ecnt].rest=; edge[ecnt].next=head[y]; head[y]=ecnt;

 }

 LL N,M,S,T;

 LL dis[maxn];

 inline bool BFS(){

     memset(dis,,sizeof(dis));

     dis[S]=;

     static queue<LL> Q;

     while(Q.size()>) Q.pop();

     Q.push(S);

     while(Q.size()>){

         LL x=Q.front(); Q.pop();

         for(LL e=head[x] ; e ; e=edge[e].next){//e表示的是边，不是点

             LL d=edge[e].to;

             if(edge[e].rest&&dis[d]==){//边权不为零且这条边通向的点的

                 dis[d]=dis[x]+;

                 Q.push(d);

                 if(d==T) return true;

             }

         }

     }

     return false;

 }

 inline LL DFS(LL x,LL flow){

     if(x==T) return flow;

     LL now=,tmp;

     for(LL e=head[x]; e ;e=edge[e].next){

         if(edge[e].rest&&dis[edge[e].to]==dis[x]+){

             tmp=DFS(edge[e].to,min(flow-now,edge[e].rest));

             edge[e].rest-=tmp;

             edge[e ^ ].rest+=tmp;

             now+=tmp;

             if(now==flow) return now;

         }

     }

     return now;

 }

 inline LL dinic(){

     LL ans=;

     while(BFS()){

         ans+=DFS(S,inf);

     }

     return ans;

 }

 LL money[maxn];

 LL tot;

 int main(){

     cin>>N>>M;

     cin>>S>>T;

     for(LL i=;i<=N;i++) scanf("%d",&money[i]);

     for(LL i=;i<=N;i++){

         tot++;

         AddEdge(tot,tot+,money[i]);

         tot++;

     }

     for(LL i=;i<=M;i++){

         LL r,l;

         cin>>r>>l;

         LL rr,ll;

         rr=(r-)*+;//出点

         ll=(l-)*+;//入点

         AddEdge(rr,ll,inf);

         ll++;

         rr--;

         AddEdge(ll,rr,inf);

     }

     S=(S-)*+;

     T=(T-)*+;

     cout<<dinic();

     return ;

 }

巴特西

1163: [Baltic2008]Mafia