bzoj3504: [Cqoi2014]危桥 网络流

一种网络流建图的思路吧，改天最好整理一波网络流建图思路

 #include <bits/stdc++.h>

 using namespace std;

 int n,h,t,a1,a2,an,b1,b2,bn,flow,now;char ch;

 int dis[],l[],d[][];char c[][];

 char getch()

 {

     for(ch=getchar();ch!='O' && ch!='N' && ch!='X';ch=getchar());

     return ch;

 }

 bool bfs()

 {

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

         dis[i]=;

     for(h=,t=,l[]=,dis[]=;h<=t;h++)

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

             if(d[l[h]][i] && !dis[i])

                 l[++t]=i,dis[i]=dis[l[h]]+;

     return dis[n+];

 }

 int dfs(int now,int maxflow)

 {

     if(now==n+) return maxflow;

     int flow=;

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

     if(dis[i]==dis[now]+ && d[now][i])

     {

         int thi=dfs(i,min(maxflow,d[now][i]));

         d[now][i]-=thi;d[i][now]+=thi;

         maxflow-=thi;flow+=thi;

         if(maxflow==) return flow;

     }

     if(flow==)

         dis[now]=-;

     return flow;

 }

 void INIT()

 {

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

         for(int j=;j<=n;j++)

         switch(c[i][j])

         {

             case'O':d[j][i]=d[i][j]=;break;

             case'N':d[j][i]=d[i][j]=flow;break;

             case'X':d[j][i]=d[i][j]=;break;

         }

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

         d[][i]=d[i][]=d[i][n+]=d[n+][i]=;

     d[a1][]=d[][a1]=an<<;d[b1][]=d[][b1]=bn<<;

     d[a2][n+]=d[n+][a2]=an<<;d[b2][n+]=d[n+][b2]=bn<<;

     now=;

 }

 int main()

 {

     while(~scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn))

     {

     a1++;a2++;b1++;b2++;

     flow=an+bn<<;

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

         for(int j=;j<=n;j++)

             c[i][j]=getch();

     INIT();

     while(now<flow && bfs()) now=now+dfs(,flow);

     if(now<flow)

     {

         puts("No");

         continue;

     }

     swap(b1,b2);

     INIT();

     while(now<flow && bfs()) now=now+dfs(,flow);

     if(now<flow)

         puts("No");

     else

         puts("Yes");

     }

     return ;

 }