hdu 4289 dinic模板

题意：有N个城市，现在城市S出现了一伙歹徒，他们想运送一些炸弹到D城市，不过警方已经得到了线报知道他们的事情，不过警察不知道他们所在的具体位置，所以只能采取封锁城市的办法来阻断暴徒，不过封锁城市是需要花费一定代价的，由于警局资金比较紧张，所以想知道如果完全阻断暴徒从S城市到达D城市的最小需要花费的代价。

思路：将每个点都拆分成2个，表示为i和i*,i是原来的起点，然后i到i*的权值为i点原来的权值，连边的时候要注意的是要从i*连接i，因为最初在起点的时候，首先要走的就是从i到i*，然后接下来一定是从i*出发回到i这一边，假设是j，然后j走j*，这样循环往复，所以边的方向都应该是i*到i。

 #include<cstdio>

 #include<string.h>

 #include<algorithm>

 #include<math.h>

 #include<queue>

 using namespace std;

 const int maxn=;

 const int inf=0x3f3f3f3f;

 int head[maxn],level[maxn];

 int num;

 void init()

 {

     num=-  ;

     memset(head,-,sizeof(head));

 }

 struct node

 {

     int v,w,next;

 }G[];

 int bfs(int s,int t)

 {

     queue<int>q;

     q.push(s);

     memset(level,-,sizeof(level));

     level[s]=;

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for(int i=head[u];i!=-;i=G[i].next){

             int v=G[i].v;

             if(G[i].w>&&level[v]==-){

                 level[v]=level[u]+;

                 q.push(v);

             }

         }

     }

    return level[t];

 }

 int dfs(int s,int t,int f)

 {

     if(s==t) return f;

     int ans=;

     for(int i=head[s];i!=-;i=G[i].next){

         int v=G[i].v;

         if(G[i].w>&&level[s]+==level[v]){

             int d=dfs(v,t,min(G[i].w,f-ans));

             if(d>){

                 G[i].w-=d;

                 G[i^].w+=d;

                 ans+=d;

                 if(ans==f) return ans;

             }

         }

     }

     return ans;

 }

 int dinic(int s,int t)

 {

     int ans=;

     while(){

         int temp=bfs(s,t);

         if(temp==-) break;

         ans+=dfs(s,t,inf);

     }

     return ans;

 }

 void build(int u,int v,int w)

 {

     num++;

     G[num].v=v;

     G[num].w=w;

     G[num].next=head[u];

     head[u]=num;

     num++;

     G[num].v=u;

     G[num].w=;

     G[num].next=head[v];

     head[v]=num;

 }

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

         init();

         int s,t;

         scanf("%d%d",&s,&t);

         t=t+n;

         int temp;

         for(int i=;i<=n;i++){

             scanf("%d",&temp);

             build(i,i+n,temp);

         }

         for(int i=;i<=m;i++){

             int u;int v;

             scanf("%d%d",&u,&v);

             build(u+n,v,inf);

             build(v+n,u,inf);

         }

         printf("%d\n",dinic(s,t));

     }

     return ;

 }

巴特西

hdu 4289 dinic模板

最新文章

热门文章