POJ1815

Problem : Friendship
Description : 一些人之间可以相互联系，但是当一个人出事后，那么与他有联系的人都会和他失去联系，同样，人与人之间的联系具有传递性，那么现在给你两个人，问你最少多少个人出事才能使得这两个人失去联系，注意，这两个人不可能出事。
Solution : 这是一个典型的求割点数目的问题，然而割点又可以通过拆点转化成割边来做，那么这个题就成了求最小割的问题了，我们的做法就是，枚举割点，如果这个点是割点那么在图中删掉这个点后跑一遍最大流后，最小割会变小，那么记录下这个点，如果最小割不变，那么这个点就不是必须的，把这个点又在图中恢复，这样下来就可以把所有的割点都找到了。拆点然后在这两个点之间连一条权值为1的边是为了每个人只会删除一次，相当于删掉这个点了，而且，这条边的在S，T之间的权值要设成INF，这是为了给出的两个人总不会出事。这条边的方向要和其他边的方向相反，这也是为了满足传递性。这题我开始用的邻接矩阵TLE，非得逼我用邻接表才AC。
Code(C++) :

#include 
#include #include 
#include 
#include #define MIN(a,b) ((a)>(b)? (b):(a))using namespace std;const int SIZE=400+50;
const int INF=0x3f3f3f3f;struct Node{int u,v;int cap;Node(){}Node(int U,int V,int Cap):u(U),v(V),cap(Cap){}
};int src,des;
vector<int> G[SIZE];
Node e[SIZE*SIZE/2];
int d[SIZE];
int cur[SIZE];
int n;
int top;int N,S,T;
bool had_erase[SIZE/2];
int MAP[SIZE/2][SIZE/2];
int t_M[SIZE/2][SIZE/2];void addedge(int u,int v,int cap)
{G[u].push_back(top);e[top++]=Node(u,v,cap);G[v].push_back(top);e[top++]=Node(v,u,0);
}void build()
{   int i,j;for(i=0;i0;n=2*N;src=0;des=n+1;addedge(src,S,INF);addedge(T+N,des,INF);for(i=1;i<=N;i++)addedge(i+N,i,1);addedge(S+N,S,INF);addedge(T+N,T,INF);for(i=1;i<=N;i++)for(j=1;j<=N;j++)if(MAP[i][j]&&i!=j)addedge(i,j+N,INF);
}bool bfs(int src,int des)
{memset(d,-1,sizeof(d));queue<int> que;que.push(src);d[src]=0;while(!que.empty()){int now=que.front();que.pop();for(int i=0;iif(tmp.cap>0&&d[tmp.v]==-1)d[tmp.v]=d[now]+1,que.push(tmp.v);}}return d[des]>=0;
}int dfs(int t,int sum,int des)
{if(t==des||!sum)return sum;int flow=0,f;for(int &i=cur[t];iif(d[tmp.v]==d[t]+1&&(f=dfs(tmp.v,MIN(sum,tmp.cap),des))>0){tmp.cap-=f;e[G[t].at(i)^1].cap+=f;sum-=f;flow+=f;if(!sum)break;}}return flow;
}int DINIC(int src,int des)
{int sum=0;while(bfs(src,des)){memset(cur,0,sizeof(cur));sum+=dfs(src,INF,des);}return sum;
}void work()
{int i,j;for(i=1;i<=N;i++)for(j=1;j<=N;j++)scanf("%d",&MAP[i][j]);if(MAP[S][T]){puts("NO ANSWER!");return ;}build();int tmp=DINIC(src,des);printf("%d\n",tmp);if(!tmp)return ;memset(had_erase,false,sizeof(had_erase));for(int L=1;L<=N;L++){if(L==S||L==T)continue;int i,j;for(i=1;i<=N;i++)for(j=1;j<=N;j++){t_M[i][j]=MAP[i][j];if(i==L||j==L)MAP[i][j]=0;}build();int t=DINIC(src,des);if(t>=tmp){for(i=1;i<=N;i++)for(j=1;j<=N;j++)MAP[i][j]=t_M[i][j];}else{--tmp;had_erase[L]=true;}if(!tmp)break;}int h[SIZE]={0};int top=0;for(i=1;i<=N;i++)if(had_erase[i])h[top++]=i;printf("%d",h[0]);for(i=1;iprintf(" %d",h[i]);puts("");
}int main()
{//freopen("in.data","r",stdin);while(~scanf("%d%d%d",&N,&S,&T))work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！