joj 2453 candy 网络流建图的题

As a teacher of a kindergarten, you have many things to do during a day, one of which is to allot candies to all children in your class. Today you have N candies for the coming M children. Each child likes different candy, and as a teacher who know them well, you can describe how the child i likes the candy j with a number Aji (Aji = 2 if the child i likes the candy j, or else Aji = 1).

The child i feels happy while ( Cij = 1 if the child i get the candy j, or else Cij = 0). Now your task is to allot the candies in such a way that makes every child happy (of course except you, ^_^).

Input
The first line of the input contains a single integer T (1 <= T <= 10), representing the number of cases that follow.

The first line of each case consists of two integers N and M (1 <= N <= 100000, 1 <= M <= 10), which are the number of candies and the number of children.

There are N lines following, the ith line containing M integers: Ai1, Ai2, Ai3, ..., AiM (1 <= Aij <= 2)

The last line of the case consists of M integers: B1, B2, B3, ..., BM (0 <= Bi <= 1000000000).

Output
For each case, if there is a way to make all children happy, display the word “Yes”. Otherwise, display the word “No”.

Sample Input
2
4 3
1 2 1
2 1 1
1 1 2
1 2 2
3 2 2
1 1
1
2
Sample Output
Yes
No

网络流，主要是建图
分配的时候肯定会优先给每个孩子分配喜欢的糖果，所以先只考虑Aij=2的孩子和糖果(i,j)。
如果Ai,j=2，那么把孩子i向糖果j连一条容量为1的边，再建立源点S，向每个孩子连一条容量为Bi/2的边（因为每个开心值为2的糖果只算1，所以孩子的B值也要先除以2），最后把每个糖果向汇点T连容量为1的边，做一次网络最大流。
假设S到孩子i的流量为fi，说明孩子i已经获得了fi*2点快乐值，还需要Bi-fi*2点，这时候f1+f2+..+fm是总共分出去的糖果数，那么还剩N-(f1+f2+..+fm)个糖果，如果这个数>=sigma(Bi-fi*2)，即剩余的糖果数大于等于孩子还需要的总共快乐值，则有解，否则无解
PS：每个孩子平均能吃10000个糖，我真是无限ORZ
以下使用的是刘汝佳白书上的DINIC算法模板做的

#include
#include
#include
#define size_num 100200
#include
#include
#define INF 1e8
using namespace std;
int child[105];
struct Dinic
{
	struct Edge{int from,to,cap,flow;};
	vector edges;
	//边表。edges[e]和edges[e+1]互为反向弧,
	//注意到e必须是偶数即是大的奇数与比他小的偶数互为反向边，即e与e^1互为反向边
	vector G[size_num];
	//领接表，G[i][j]表示节点i的第j条边在e数组中的序号
	void add_edge(int from,int to,int cap)
	{
		edges.push_back((Edge){from,to,cap,0});//加入正向边
		edges.push_back((Edge){to,from,0,0});//加入反向边
		int m=edges.size();
		G[from].push_back(m-2);//存的是边的位子
		G[to].push_back(m-1);//貌似有一种静态链表的感觉
	}
	int s,t;//源点编号和汇点编号
	bool vis[size_num];//bfs时使用
	int d[size_num];//从起点到i的距离
	int cur[size_num];//当前弧的下标
	void init()
	{
		edges.clear();
		for(int i=0;i q;
		q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!q.empty())
		{
			int x=q.front();q.pop();
			for(int i=0;ie.flow)
				{
					vis[e.to]=1;
					d[e.to]=d[x]+1;
					q.push(e.to);
				}

			}
		}
		return vis[t];
	}

	//dfs
	int dfs(int x,int a)
	{
		if (x==t||a==0) return a;
			int flow=0,f;
		for(int &i=cur[x];i0)
			{
				e.flow+=f;//增加正向的流量
				edges[G[x][i]^1].flow-=f;//减少反向的流量
				flow+=f;
				a-=f;
				if(a==0) break;
			}
		}

		return flow;
	}
	//
	int maxflow(int s,int t)
	{
		this->s=s;this->t=t;
		int flow=0;
		while(bfs())
		{
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INF);
		}
		return flow;
	}
}solve;
void read()
{
	solve.init();
	int n,m;//糖果数量和孩子的数量
	cin>>n>>m;
	int s=0,t=1+m+n;
	//solve->n=t+1;
	//1->m表示孩子，m+1->m+n表示糖果
	for(int i=1;i<=n;i++)
	{
		solve.add_edge(i+m,t,1);
		for(int j=1;j<=m;j++)
		{
			int temp;
			cin>>temp;
			if(temp==2)
				solve.add_edge(j,m+i,1);
		}
	}
	long long sum=0;
	for(int i=1;i<=m;i++)
	{
		cin>>child[i];
		sum+=child[i];
		solve.add_edge(s,i,child[i]/2);
	}
	int f=solve.maxflow(s,t);
	int yu=n-f;
	if(sum<=yu+f*2)
		cout<<"Yes\n";
	else
		cout<<"No\n";
}

int main()
{

	int T;cin>>T;
	while(T--)
	read();
	return 0;
}