| Time Limit: 2000MS | Memory Limit: 20000K | |
| Total Submissions: 8640 | Accepted: 2412 |
Description
Input
Output
Sample Input
3 1 3 1 1 0 1 1 1 0 1 1
Sample Output
1 2
题意：给定一个图，求去掉最少的顶点，使得s与t不连通，答案有多个时，按输出字典序最小的。
假如s与t直接连通，则无解，
否则拆点，一个点拆成入度，出度两个点，之间s，t两个点流量为无穷大，其他点为1，然后建图，跑一遍最大流，
然后从小到大枚举除s，t之外的点，用一个数组标记把点去掉，建图跑最大流，假如流量减少，则说明这个点需要去掉，否则这个点无关紧要，不能去掉，
然后输出答案即可。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/3/8 16:40:10
File Name :1718.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=1010;
const int maxm=400010;
struct Edge{
int to,next,cap,flow;
Edge(){};
Edge(int _next,int _to,int _cap,int _flow){
next=_next;to=_to;cap=_cap;flow=_flow;
}
}edge[maxm];
int head[maxn],tol,gap[maxn],dep[maxn],cur[maxn];
void addedge(int u,int v,int flow){
edge[tol]=Edge(head[u],v,flow,0);head[u]=tol++;
edge[tol]=Edge(head[v],u,0,0);head[v]=tol++;
}
int Q[maxn];
void bfs(int start,int end){
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]++;int front=0,rear=0;
dep[end]=0;Q[rear++]=end;
while(front!=rear){
int u=Q[front++];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(dep[v]==-1&&edge[i].cap)
Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
}
}
}
int S[maxn];
int sap(int start,int end,int N){
bfs(start,end);
memcpy(cur,head,sizeof(head));
int top=0,u=start,ans=0;
while(dep[start]<N){
if(u==end){
int MIN=INF,id;
for(int i=0;i<top;i++)
if(MIN>edge[S[i]].cap-edge[S[i]].flow)
MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
for(int i=0;i<top;i++)
edge[S[i]].flow+=MIN,edge[S[i]^1].flow-=MIN;
ans+=MIN,top=id,u=edge[S[top]^1].to;
continue;
}
bool flag=0;int v;
for(int i=cur[u];i!=-1;i=edge[i].next){
v=edge[i].to;
if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
flag=1;cur[u]=i;break;
}
}
if(flag){
S[top++]=cur[u];u=v;continue;
}
int MIN=N;
for(int i=head[u];i!=-1;i=edge[i].next)
if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<MIN)
MIN=dep[edge[i].to],cur[u]=i;
if(--gap[dep[u]]==0)break;gap[dep[u]=MIN+1]++;
if(u!=start)u=edge[S[--top]^1].to;
}
return ans;
}
int flag[400][400],mark[500];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,s,t;
while(~scanf("%d%d%d",&n,&s,&t)){
memset(head,-1,sizeof(head));tol=0;
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++){
if(i==s||i==t)addedge(i,i+n,INF);
else addedge(i,i+n,1);
for(int j=1;j<=n;j++){
scanf("%d",&flag[i][j]);
if(flag[i][j]&&i!=j)
addedge(i+n,j,INF);
}
}
if(flag[s][t]){
printf("NO ANSWER!\n");
continue;
}
vector<int> ans;
addedge(0,s,INF);addedge(t+n,2*n+1,INF);
int pre=sap(0,2*n+1,4*n+10);
for(int i=1;i<=n;i++){
if(i==s||i==t)continue;
mark[i]=1;
memset(head,-1,sizeof(head));tol=0;
for(int j=1;j<=n;j++){
if(mark[j])continue;
if(j!=s&&j!=t)addedge(j,j+n,1);
else addedge(j,j+n,INF);
}
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(flag[j][k]&&k!=j&&!mark[j]&&!mark[k])
addedge(j+n,k,INF);
}
}
addedge(0,s,INF);addedge(t+n,2*n+1,INF);
int ret=sap(0,2*n+1,4*n+10);
if(ret<pre)ans.push_back(i),pre=ret;
else mark[i]=0;
}
printf("%d\n",ans.size());
if(ans.size()){
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i],i==ans.size()-1?‘\n‘:‘ ‘);
}
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/20792079