http://www.zybbs.org/JudgeOnline/problem.php?id=1585

第一的那个30MS……还是PAS……是单纯形神犇还是……

一开始构图各种2。先拆除1以外的所有点，拆成入点与出点，入点连向出点边权为1。原先的每条边双向连接边权为无穷大的边建超级汇点T，对每个报告点入点（我一开始就忘了这里应该是入点，因为这个点不能被割掉）连向T边权为无穷大。然后扫一遍就能很快AC了……

#include <stdio.h>
__inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}int n,m,s,t,dis[6002],gap[23001],flow=0,delta,x,y,z,i,stp=0;
struct edge{int x,y,w;struct edge *opp,*next;}*map[6002],*neck[6002],*from[6002],*cur[6002],st[92000],*f;
__inline addedge(x,y,z){
	st[stp^1].y=st[stp].x=x;st[stp].y=st[stp^1].x=y;
	st[stp].next=map[x];st[stp^1].next=map[y];
	(st[stp^1].opp=map[x]=st+stp)->w=z;st[stp].opp=map[y]=st+(stp^1);
	stp+=2;
}main(){
	int k;
	gap[0]=n=(getint()<<1)+2;
	m=getint();t=getint();
	for(i=n-2;i>0;i-=2)addedge(i,i^1,1);
	for(i=0;i<m;i++){
		x=getint()<<1;y=getint()<<1;
		addedge(x^1,y,100000);
		addedge(y^1,x,100000);
	}while(t--)addedge(getint()<<1,0,100000);
	for(m+=n,i=s=3,t=0;dis[s]<=m;){
		for(cur[i]||(cur[i]=map[i]);cur[i];cur[i]=cur[i]->next)if(cur[i]->w&&dis[cur[i]->y]+1==dis[i]){
			neck[(from[cur[i]->y]=cur[i])->y]=s==i?cur[i]:neck[i]->w>cur[i]->w?cur[i]:neck[i];
			if(t==(i=cur[i]->y)){
				for(flow+=delta=neck[t]->w;i!=s;i=from[i]->x)from[i]->w-=delta,from[i]->opp->w+=delta;
				i=neck[t]->x;
			}break;
		}if(!cur[i]){
			if(!--gap[dis[i]])break;
			for(dis[i]=m,f=map[i];f;f=f->next)if(f->w&&dis[f->y]<dis[i])dis[i]=dis[(cur[i]=f)->y];
			gap[++dis[i]]++;
			i=i==s?s:from[i]->x;
		}
	}printf("%d\n",flow);
	return 0;
}

• inline
• block