BZOJ-3504 [Cqoi2014]危桥最大流

题面

题意:50个城市,告诉你,有的城市之间有双向边,告诉你一些边只能走2次,一些可以走无限次,

给你起点a1,终点a2,起点b1,终点b2,问你能否从a1到a2往返an次,同时也能b1到b2往返bn次

题解:首先考虑一对点的时候,a1到a2的路要往返an次,也就相当于需要经过a1->a2 an次,a2->a1 an次,

　　但是我们想,因为最差的路也可以走2次,所以回来的路,一定可以和原来去的路选的一样,

　　那么现在其实问题变成了:a1要去a2 an次,所以其实对于每个S->a1 a2->T 都连an*2的边

对于只能走2次的路,build(u,v,2);可以走无限次的,build(u,v,inf);

现在对于a1,a2,如果这个网络流能满流,则说明可行.

那像a1,a2一样加上b1,b2是不是直接就行了呢？

否啊(没看题解也没想到)

因为可能有a1的流给了b1,发现大家采用的解决办法是swap(b1,b2)再来一次(有丶巧妙),如果都可行则可行

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 550
  4 #define M 3000
  5 #define inf 0x7fffffff/3
  6 namespace Dinic
  7 {
  8     int head[N],head2[N],p=1;
  9     struct Rec
 10     {
 11         int go,nex,c;
 12     }eg[M*2];
 13     void build(int a,int b,int c)
 14     {
 15         eg[++p]=(Rec){b,head[a],-c};
 16         head[a]=p;
 17         eg[++p]=(Rec){a,head[b],0};
 18         head[b]=p;
 19     }
 20     int dis[N],Q[N],s[N],S,T,stop,ans;
 21     bool bfs()
 22     {
 23         memset(dis,0,sizeof(dis));
 24         dis[T]=1;
 25         Q[1]=T;
 26         for (int p1=1,p2=1;p1<=p2;p1++)
 27         {
 28             for (int i=head[Q[p1]];i;i=eg[i].nex)
 29                 if (eg[i^1].c<0&&!dis[eg[i].go])
 30                 {
 31                     dis[eg[i].go]=dis[Q[p1]]+1;
 32                     Q[++p2]=eg[i].go;
 33                 }
 34         }
 35         if (!dis[S]) return false;
 36         memcpy(head2,head,sizeof(head));
 37         return true;
 38     }
 39     bool dinic(int p,int top)
 40     {
 41         if (p==T)
 42         {
 43             int x=inf;
 44             for (int i=1;i<=top-1;i++) if (-eg[s[i]].c<x) x=-eg[s[i]].c,stop=i;
 45             for (int i=1;i<=top-1;i++) eg[s[i]].c+=x,eg[s[i]^1].c-=x;
 46             ans+=x;
 47             return true;
 48         }
 49         for (int &i=head2[p];i;i=eg[i].nex)
 50         {
 51             if (eg[i].c<0&&dis[eg[i].go]==dis[p]-1)
 52             {
 53                 s[top]=i;
 54                 if (dinic(eg[i].go,top+1)&&top!=stop) return true;
 55             }
 56         }
 57         return false;
 58     }
 59     int ask()
 60     {
 61         ans=0;
 62         while (bfs()) dinic(S,1);
 63         return ans; 
 64     }
 65     void init(int _S,int _T){
 66         S=_S,T=_T;
 67     }
 68 }
 69 using namespace Dinic;
 70 int ss,tt,n,a1,a2,an,b1,b2,bn,flag;
 71 char se[55][55];
 72 void clear()
 73 {
 74     p=1;
 75     memset(head,0,sizeof(head));
 76 }
 77 void why()
 78 {
 79     clear();
 80     build(ss,a1,2*an);
 81     build(ss,b1,2*bn);
 82     build(a2,tt,2*an);
 83     build(b2,tt,2*bn);      
 84     for (int i=1;i<=n;i++)
 85     {
 86         for (int j=1;j<=n;j++)
 87             if (se[i][j]=='O') build(i,j,2);else
 88             if (se[i][j]=='N') build(i,j,inf);
 89     } 
 90     if (ask()!=an+bn+an+bn) flag=1;
 91 }
 92 int main()
 93 {
 94     while (scanf("%d",&n)!=EOF)
 95     {
 96         flag=0;
 97         scanf("%d%d%d",&a1,&a2,&an);
 98         scanf("%d%d%d",&b1,&b2,&bn);
 99         for (int i=1;i<=n;i++)scanf("%s",se[i]+1);
100         a1++;a2++;b1++;b2++;
101         ss=n+1;tt=n+2;
102         init(ss,tt);
103         why();
104         if (flag)printf("No
");else 
105         {
106             swap(b1,b2);
107             why();
108             if (flag)printf("No
");else printf("Yes
");    
109         } 
110     }
111 }

Anderyi!

BZOJ-3504 [Cqoi2014]危桥 最大流

BZOJ-3504 [Cqoi2014]危桥最大流