题目分析：数据比较强，用来测模版的。这题用hungry跑着会比较吃力，所以用hopcroft-karp算法。这个算法较hungry高效是因为每次bfs找到一个增广路集，然后用dfs进行多路增广，同时找多条增广路，从而效率大增。其实怎么看hk算法都是个没有边权的dinic啊。
参照着wikipedia 敲了一个hk，效率貌似不高啊。。。
详情请见代码：
#include#include #include using namespace std; const int N = 50001; const int M = 150001; const int inf = 0x3f3f3f3f; int head[N]; struct node { int to,next; }g[M]; int m,n,p,num; int matchx[N],matchy[N],que[N],dis[N]; void build(int s,int e) { g[num].to = e; g[num].next = head[s]; head[s] = num ++; } bool bfs() { int i,j; int front,rear; front = rear = 0; for(i = 1;i <= n;i ++) { if(!matchx[i]) { dis[i] = 0; que[rear ++] = i; } else dis[i] = inf; } dis[0] = inf; while(front != rear) { int u = que[front ++]; if(front == N) front = 0; for(i = head[u];~i;i = g[i].next) { int v = g[i].to; if(dis[matchy[v]] == inf) { dis[matchy[v]] = dis[u] + 1; que[rear ++] = matchy[v]; if(rear == N) rear = 0; } } } return dis[0] != inf; } bool dfs(int u) { int i,v; for(i = head[u];~i;i = g[i].next) { v = g[i].to; if(dis[matchy[v]] == dis[u] + 1) if(matchy[v] == 0 || dfs(matchy[v])) { matchx[u] = v; matchy[v] = u; return true; } } dis[u] = inf; return false; } void Hopcroft_Karp() { memset(matchx,0,sizeof(matchx)); memset(matchy,0,sizeof(matchy)); int ans = 0; while(bfs()) { for(int i = 1;i <= n;i ++) if(!matchx[i]) if(dfs(i)) ans ++; } printf("%d\n",ans); } int main() { int a,b; while(scanf("%d",&n) != EOF) { memset(head,-1,sizeof(head)); num = 1; scanf("%d%d",&m,&p); while(p --) { scanf("%d%d",&a,&b); build(a,b); } Hopcroft_Karp(); } return 0; }