有限电视网络

给定无向图 最少去掉多少个点可以让图不连通

如果有割点 那么答案是1
所以不能用tarjan做法 而应该采用网络流做法 题目这种要求和最小割很类似

#include 
#include 
#include 
#include 
#define pa pair
#define mp make_pair
#define fs first
#define sc second
using namespace std;

const int N=105;
const int M=5000;
const int INF=0x3f3f3f3f;

int read()
{
	int x=0,f=0,c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}

struct Edge
{
	int to,next,w;
}e[M];
int head[N],cnt=1;
void _add(int a,int b,int c){  e[++cnt]=(Edge){b,head[a],c}; head[a]=cnt;}
void add(int a,int b,int c){ _add(a,b,c);_add(b,a,0);}
int n,m,S,T;
bool atl[55][55];
pa p[M];

queue q;int d[N];
bool bfs()
{
	while(q.size()) q.pop();
	memset(d,0,sizeof d);
	q.push(S+n); d[S+n]=1;
	while(q.size())
	{
		int x=q.front(); q.pop();
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(!e[i].w||d[y]) continue;
			d[y]=d[x]+1; q.push(y);
			if(y==T) return 1;
		}
	}
	return 0;
}

int dinic(int x,int flow)
{
	if(x==T) return flow;
	int rest=flow;
	for(int i=head[x];i&&rest;i=e[i].next)
	{
		int y=e[i].to;
		if(e[i].w&&d[y]==d[x]+1)
		{
			int k=dinic(y,min(rest,e[i].w));
			if(!k) d[y]=0;
			e[i].w-=k; e[i^1].w+=k; rest-=k;
		}
	}
	return flow-rest;
}

int main()
{	
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(atl,0,sizeof atl);	
		if(!m&&n==1){printf("%d\n",n);continue;}
		getchar();
		for(int i=1;i<=m;i++)
		{
			getchar(); 
			int x=read()+1;int y=read()+1; 
			atl[x][y]=1; atl[y][x]=1;
			p[i]=mp(x,y);
		}
		int ans=INF,flow=0,maxflow=0;
		for(S=1;S<=n;S++)
			for(T=S+1;T<=n;T++)
			{

				if(atl[S][T]) { ans=min(ans,n); continue;}		
				
				memset(head,0,sizeof head); cnt=1;	
				for(int i=1;i<=m;i++) 
					add(p[i].fs+n,p[i].sc,INF),add(p[i].sc+n,p[i].fs,INF);
				for(int i=1;i<=n;i++) 
					if(i!=S&&i!=T) add(i,i+n,1);	
				maxflow=0; 
					
				while(bfs()) 
					while(flow=dinic(S+n,INF)) maxflow+=flow;	
			
				ans=min(ans,maxflow);
			}
		if(ans==INF) ans=0;
		printf("%d\n",ans);
	}
	return 0;
}

注意:
//S点T点不拆开
//每次都必须重新建图 因为dinic涉及到了图的修改,对应的maxflow也要清零
//网络流中 每一个add视为一条有向边 因此如果是双向边的话 还需要加两边边