最开始做的时候,思路是:

s –inf–> 男生i –k–> 男生i拆点 –1–> 不喜欢女生j –k–> 女生j –inf–> t

s –inf–> 男生i –1–> 喜欢的女生j –inf—> t

本来相一次流过去,检查 女生—->t 最小值是多少,就是答案。

但是我忽略了一个问题,网络流的性质是满流与否,可能流的方式是不一样的,所以没过。看解题报告之后,知道了用二分来写。也就是上面inf的地方换成二分的值。

但是各种控制不好,犯了不少低级错误,数组忘记重置,二分退出条件什么的,汗颜。

#include <cstdio>
#include <cstring>
#define CC(m,what)		memset(m,what,sizeof(m))
#define FOR(i,a,b)		for( int i = (a) ; i < (b) ; i ++ )
#define FF(i,a)			for( int i = 0 ; i < (a) ; i ++ )
template<class T> inline void checkmin(T &a,T b)	{if(a == -1 || a > b)a = b;}
#define M 1000
int maze[M][M];
int gap[M],dis[M],pre[M],cur[M];
int sap(int s,int t,int nodenum) {
	CC(cur,0);CC(dis,0);CC(gap,0);
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = nodenum;
	while(dis[s] < nodenum) {
loop:		FOR(v,cur[u],nodenum) if(maze[u][v] && dis[u] == dis[v] + 1) {
			checkmin(aug,maze[u][v]);
			pre[v] = u;
			u = cur[u] = v;
			if(v == t) {
				maxflow += aug;
				for(u = pre[u];v != s;v = u,u = pre[u]) {
					maze[u][v] -= aug;
					maze[v][u] += aug;
				}
				aug = -1;
			}
			goto loop;
		}
		int mindis= nodenum-1;
		FF(v,nodenum) if(maze[u][v] && mindis> dis[v]) {
			cur[u] = v;
			mindis= dis[v];
		}
		if((--gap[dis[u]])== 0)	break;
		gap[dis[u] = mindis+1] ++;
		u = pre[u];
	}
	return maxflow;
}

int mz[M][M];
int main(){
	int ts,cs,i,j;
	int n,m,k,a,b,s,t;
	int left,mid,right,ans;
	const int inf=99999999;
	bool fg;
	scanf("%d",&ts);
	for(cs=1;cs<=ts;cs++){
		scanf("%d%d%d",&n,&m,&k);
		s=0;t=4*n+1;
		memset(mz,0,sizeof(mz));
		for(i=0;i<m;i++){
			scanf("%d%d",&a,&b);
			mz[a][n+b]=1;
		}
		left=0;
		right=n;
		while(left<=right){
			mid=(left+right)>>1;
//			printf("%d %d %dn",left,mid,right);
			memset(maze,0,sizeof(maze));
			for(i=1;i<=n;i++){
				maze[s][i]=mid;
				maze[i][2*n+i]=k;
				maze[3*n+i][n+i]=k;
				maze[n+i][t]=mid;
				for(j=1;j<=n;j++){
					if(mz[i][n+j]!=1){
						maze[2*n+i][3*n+j]=1;
					}else{
						maze[i][n+j]=1;
					}
				}
			}
			if(sap(s,t,t+1)==n*mid){
				left=mid+1;
				ans=mid;
			}else{
				right=mid-1;
			}
		}
		printf("%dn",ans);
	}
	return 0;
}