窝才不说这应该是二分图匹配然而窝用网络流的板子过掉了。。。

为了对得起标题边上的网络流和老早以前做过的一道纯网络流的题目，窝又无聊地做了一遍纯网络流。

要设定一个超级源点和超级汇点，然而这并没有什么难度。

直接上代码吧

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

queue <int> que;
int NM,n,m,x,y,ans;
int pre[500],flow[500];
int road[500][500];

int BFS(int xx,int yy)
{
	while (!que.empty()) que.pop();
	for (int i=1;i<=NM+2;++i) pre[i]=-1;
	que.push(xx);
	pre[xx]=0,flow[xx]=0x7fffffff;
	while (!que.empty())
	{
		int h=que.front(); que.pop();
		if (h==yy) break;
		for (int i=1;i<=NM+2;++i)
		{
			if (i!=xx && road[h][i]>0 && pre[i]==-1)
			{
				que.push(i);
				flow[i]=min(flow[h],road[h][i]);
				pre[i]=h;
			}
		}
	}
	if (pre[yy]==-1) return -1;
	else return flow[yy];
}

int MAX_FLOW(int xx,int yy)
{
	int sum=0;
	int minn=0;
	while ((minn=BFS(xx,yy))!=-1)
	{
		int k=yy;
		while (k!=xx)
		{
			int la=pre[k];
			road[la][k]-=1;
			road[k][la]+=1;
			k=la;
		}
		sum+=minn;
	}
	return sum;
}


int main()
{
	freopen("1100.in","r",stdin); freopen("1100.out","w",stdout);
	scanf("%d%d",&m,&n);
	memset(road,0,sizeof(road));
	scanf("%d%d",&x,&y);
	while (x!=-1 && y!=-1)
	{
		road[x][y]=1;
		scanf("%d%d",&x,&y);
	}
	NM=n+m;
	for (int i=1;i<=m;++i) road[NM+1][i]=1;
	for (int i=m+1;i<=n;++i) road[i][NM+2]=1;
	ans=MAX_FLOW(NM+1,NM+2);
	if (ans==0) printf("No Solution!"); else
	printf("%d\n",ans);
	_fcloseall();
	return 0;
}

算了，还是不吐槽第一遍写网络流的线段树大师吧

PS. USACO上也有一道水水的，标号为4.2.1（有木有感觉两段代码基本上一模一样哎）

附上代码

/*
ID: lujiaxi1
PROG: ditch
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#define maxn 201

using namespace std;

int ca[maxn][maxn],pre[maxn],flow[maxn];
int n,m;

queue<int> que;

int BFS(int a,int b)
{
	while (!que.empty()) que.pop();
	for (int i=1;i<=m;++i)
	{
		pre[i]=-1;
	}
	pre[a]=0;
	flow[a]=INT_MAX;
	que.push(a);
	while (!que.empty())
	{
		int k=que.front();
		que.pop();
		if (k==b) break;
		for (int i=1;i<=m;++i)
		{
			if (i!=a && ca[k][i]>0 && pre[i]==-1)
			{
				pre[i]=k;
				flow[i]=min(ca[k][i],flow[k]);
				que.push(i);
			}
		}
	}
	if (pre[b]==-1) return -1;
	else return flow[b];
}

int MAX_flow(int a,int b)
{
	int sum=0;
	int minn=0;
	while ((minn=BFS(a,b))!=-1)
	{
		int k=b;
		while (k!=a)
		{
			int la=pre[k];
			ca[la][k]-=minn;
			ca[k][la]+=minn;
			k=la;
		}
		sum+=minn;
	}
	return sum;
}

int main()
{
	freopen("ditch.in", "r", stdin);
    freopen("ditch.out", "w", stdout);
	cin>>n>>m;
	for (int i=1;i<=n;++i)
	{
		int a,b,c;
		cin>>a>>b>>c;
		ca[a][b]+=c;
	}
	cout<<MAX_flow(1,m)<<endl;
	fclose(stdin); fclose(stdout);
	return 0;
}