poj 1815 Friendship 字典序最小+最小割

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://poj.org/problem?id=1815

In modern society, each person has his own friends. Since all the people are very busy, they communicate with each other only by phone. You can assume that people A can keep in touch with people B, only if
1. A knows B's phone number, or
2. A knows people C's phone number and C can keep in touch with B.
It's assured that if people A knows people B's number, B will also know A's number.

Sometimes, someone may meet something bad which makes him lose touch with all the others. For example, he may lose his phone number book and change his phone number at the same time.

In this problem, you will know the relations between every two among N people. To make it easy, we number these N people by 1,2,...,N. Given two special people with the number S and T, when some people meet bad things, S may lose touch with T. Your job is to compute the minimal number of people that can make this situation happen. It is supposed that bad thing will never happen on S or T.

题目描述：n个人，给出一些关系（两个人之间直接联系或可以间接联系），现在破坏一些人，使S和T这两个人不能联系。求出最小的人数（输出字典序最小的方案）。

算法分析：最小割解之，这个不用说了。重点在于怎么求解字典序最小：由于节点较少，我们可以一一枚举节点u，然后去掉u->u'后求解最小割是否会使最小割变小，是则必须删掉此边。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 0x7fffffff

 using namespace std;

 const int maxn=,M=;

 int n,from,to;

 struct node

 {

     int v,flow;

     int next;

 } edge[M*],save[M*];

 int head[maxn],edgenum;

 void add(int u,int v,int flow)

 {

     edge[edgenum].v=v ;edge[edgenum].flow=flow ;

     edge[edgenum].next=head[u] ;head[u]=edgenum++;

     edge[edgenum].v=u ;edge[edgenum].flow=;

     edge[edgenum].next=head[v] ;head[v]=edgenum++;

 }

 int d[maxn];

 int bfs()

 {

     memset(d,,sizeof(d));

     d[from]=;

     queue<int> Q;

     Q.push(from);

     while (!Q.empty())

     {

         int u=Q.front() ;Q.pop() ;

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

         {

             int v=edge[i].v;

             if (!d[v] && edge[i].flow)

             {

                 d[v]=d[u]+;

                 Q.push(v);

                 if (v==to) return ;

             }

         }

     }

     return ;

 }

 int dfs(int u,int flow)

 {

     if (u==to || flow==) return flow;

     int cap=flow;

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

     {

         int v=edge[i].v;

         if (d[v]==d[u]+ && edge[i].flow)

         {

             int x=dfs(v,min(cap,edge[i].flow));

             edge[i].flow -= x;

             edge[i^].flow += x;

             cap -= x;

             if (cap==) return flow;

         }

     }

     return flow-cap;

 }

 int dinic()

 {

     int ans=;

     while (bfs()) ans += dfs(from,inf);

     return ans;

 }

 int an[maxn][maxn];

 int main()

 {

     while(scanf("%d%d%d",&n,&from,&to)!=EOF)

     {

         bool flag=false;

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

         {

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

             {

                 scanf("%d",&an[i][j]);

             }

         }

         if(an[from][to])

         {

             printf("NO ANSWER!\n");

             continue;

         }

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

         edgenum=;

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

         {

             if (i!=from && i!=to)

                 add(i,i+n,);

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

             {

                 if (an[i][j]&&i!=j)

                 {

                     if (i==from)

                         add(i,j,inf);

                     else if (i!=to)

                         add(i+n,j,inf);

                 }

             }

         }

         memcpy(save,edge,sizeof(node)*edgenum);

         int ans=dinic();

         printf("%d\n",ans);

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

         {

             if (i!=from && i!=to)

                 for (int j=head[i] ;j!=- ;j=edge[j].next)

                 {

                     if (edge[j].flow== && edge[j].v==i+n)

                     {

                         save[j].flow=save[j^].flow=;

                         memcpy(edge,save,sizeof(node)*edgenum);

                         if (dinic()!=ans-)

                         {

                             save[j].flow=;

                             save[j^].flow=;

                             continue;

                         }

                         if (flag)

                             printf(" ");

                         else

                             flag=true;

                         printf("%d",i);

                         ans--;

                         break;

                     }

                 }

         }

         printf("\n");

     }

     return ;

 }