#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;

const int THRES = 200;

const int SSS = 2147483647;
const int TTT = -2147483648;
int N, M;
int graph[THRES][THRES] = {{0}};
bool s[THRES] = {0}, t[THRES] = {0};//false表示可用

void init(){
	for(int i = 0; i < THRES; i++){
		for(int j = 0; j < THRES; j++){
			graph[i][j] = 0;
		}
	}
	for(int i = 0; i < THRES; i++) s[i]=t[i]=0;
}

bool pushflow(){
	//如果push不了，返回false
	queue<int> bfs;
	bool getT = false;
	int noT;
	int S[THRES] = {0}, T[THRES] = {0};
	for(int i = 1; i < N; i++){
		if(!s[i]){
			S[i] = SSS;
			bfs.push(i);
		}
	}
	while(!bfs.empty()){
		int cur = bfs.front();
		bfs.pop();
		if(cur > 0){
			//是s这边的点
			for(int j = 1; j <= M; j++){
				if(graph[cur][j] == 1 && T[j] == 0){
					bfs.push(-j);
					T[j] = cur;
				}
			}
		}
		else{
			//是t这边的点
			int j = -cur;
			if(!t[j]){
				getT = true;
				noT = cur;
				break;
			}
			for(int i = 1; i < N; i++){
				if(graph[i][j] == -1 && S[i] == 0){
					bfs.push(i);
					S[i] = cur;
				}
			}
		}
	}
	if(!getT) return false;
	t[-noT] = true;
	int TtoS = 1;
	while(1){
		if(TtoS){
			//push路径当前从S端到T端
			int noS = T[-noT];
			graph[noS][-noT] = -1;
			noT = noS;
		}
		else{
			//从T端到S端
			int noS = S[noT];
			if(noS == SSS){
				s[noT] = true;
				break;
			}
			graph[noT][-noS] = 1;
			noT = noS;
		}
		TtoS = 1 - TtoS;
	}
	return true;
}


int main() {
	int t;
	scanf("%d", &t);
	for(int ii = 0; ii < t; ii++){
		init();
		int str;
		scanf("%d%d", &N, &str);
		N++;
		M=N-1;
		for(int i = 0; i < str; i++){
			int a,b;
			scanf("%d%d", &a, &b);
			graph[a][b] = 1;
		}
		int cnt = 0;
		while(pushflow()){
			cnt++;
		}
		printf("%d\n", M-cnt);
	}
	return 0;
}

• Re:好吧我承认这是个最大流模板题 (2046) Ash1mar 2017-05-01 14:41:10