题意:
有一群恐怖分子要从起点 st 到 en 城市集合, 你要在路程中的城市阻止他们, 使得他们全部都被抓到(当然 st 城市, en 城市也可以抓捕). 在每一个城市抓捕都有一个花费, 你要找到花费最少是多少.
题解:
- // 首先这一道题我原本是想这用 bfs 来做, 因为这就相当于一棵树, 你就只需要找出来怎么把它截断就可以
- // 但是这种方法我没有尝试, 我还是用的最大流. 那个每一个城市可以拆点成两个, 然后这两个城市之间的
- // 权值设为这个城市的驻扎成本, 然后如果两个城市相连, 比如 x 和 y 相连, 那么就可以建 (x+n,y,INF),(y+n,x,INF) 这
- // 两条边. 然后跑最大流就可以了
- // 即使题目让你求都在哪几个点设防, 你也可以写出来. 因为跑完最大流之后要设防的点的流量都变成了 0
- #include<stdio.h>
- #include<string.h>
- #include<iostream>
- #include<algorithm>
- #include<queue>
- using namespace std;
- const int maxn=1200;
- const int INF=0x3f3f3f3f;
- int head[maxn],cnt,st,en,dis[maxn],cur[maxn];
- struct edge
- {
- int v,next,c,flow;
- } e[maxn*maxn];
- void add_edge(int x,int y,int z)
- {
- e[cnt].v=y;
- e[cnt].c=z;
- e[cnt].flow=0;
- e[cnt].next=head[x];
- head[x]=cnt++;
- }
- bool bfs()
- {
- memset(dis,0,sizeof(dis));
- dis[st]=1;
- queue<int>r;
- r.push(st);
- while(!r.empty())
- {
- int x=r.front();
- r.pop();
- for(int i=head[x]; i!=-1; i=e[i].next)
- {
- int v=e[i].v;
- if(!dis[v] && e[i].c>e[i].flow)
- {
- dis[v]=dis[x]+1;
- r.push(v);
- }
- }
- }
- return dis[en];
- }
- int dinic(int s,int limit)
- {
- if(s==en || !limit) return limit;
- int ans=0;
- for(int &i=cur[s]; i!=-1; i=e[i].next)
- {
- int v=e[i].v,feed;
- if(dis[v]!=dis[s]+1) continue;
- feed=dinic(v,min(limit,e[i].c-e[i].flow));
- if(feed)
- {
- e[i].flow+=feed;
- e[i^1].flow-=feed;
- limit-=feed;
- ans+=feed;
- if(limit==0) break;
- }
- }
- if(!ans) dis[s]=-1;
- return ans;
- }
- int main()
- {
- int s,d,n,m;
- while(~scanf("%d%d",&n,&m))
- {
- scanf("%d%d",&s,&d);
- memset(head,-1,sizeof(head));
- cnt=0;
- int x;
- for(int i=1;i<=n;++i)
- {
- scanf("%d",&x);
- add_edge(i,i+n,x);
- add_edge(i+n,i,0);
- }
- st=s;
- en=d+n;
- while(m--)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- add_edge(x+n,y,INF);
- add_edge(y,x+n,0); // 反向边也要建
- add_edge(y+n,x,INF);
- add_edge(x,y+n,0);
- }
- int ans=0;
- while(bfs())
- {
- for(int i=0; i<=2*n; i++)
- cur[i]=head[i];
- ans+=dinic(st,INF);
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3283436.html