【转】原文：http://blog.csdn.net/wangjian8006/article/details/7926040
题目大意：爱丽丝要拍电影，有n部电影，规定爱丽丝每部电影在每个礼拜只有固定的几天可以拍电影，只可以拍前面w个礼拜，并且这部电影要拍d天,问爱丽丝能不能拍完所有的电影
第一行代表有多少组数据
对于每组数据第一行代表有n部电影
接下来2到n+1行，每行代表一个电影，每行9个数，前面7个数，1代表拍，0代表不拍，第8个数代表要拍几天，第9个数代表有几个礼拜时间拍
解题思路：
这题可以看做成二分图多重匹配，也可以用网络流实现，主要是建图，将图建好了就好说了
用s=0表示源点,t=371表示汇点
将371看做汇点的原因是，1-350表示每天,因为最多有50个星期....
351-370表示电影,因为电影最多只有20部
源点指向每部电影,最大容量为这部电影所拍摄的天数
电影指向天数,因为每天只能拍一部电影,若这天可以拍这部电影就表示最大容量为1
天数都指向汇点,最大容量都为1
这样建好图之后就可以直接从源点到汇点求最大流，看最大流是否等于每个电影天数相加只和，相等则可以拍完，不等则拍不完
/*
Memory 708K
Time 47MS
*/
#include <iostream>
#include <queue>
using namespace std;
#define min(a,b) (a>b?b:a)
#define MAXV 372
#define MAXINT INT_MAX int rc[MAXV][10]; //1到7为星期几,8是拍摄几天,9是在多少周内完成
int r[372][372]; //容量
int s,t,n,max_flow; //表示s源点与t汇点,n部电影 int parent[MAXV];
int dis[MAXV]; void read_graph(){
int i,j,k;
for(i=1;i<=n;i++){
r[0][i+350]=rc[i][8]; for(j=1;j<=7;j++){
if(rc[i][j]){
for(k=0;k<rc[i][9];k++)
r[i+350][j+k*7]=1;
}
}
} for(i=1;i<=350;i++) r[i][371]=1;
} int bfs(){
int k;
queue<int> q;
memset(dis,-1,sizeof(dis));
dis[t]=0; q.push(t);
while(!q.empty()){
k=q.front();
q.pop();
for(int i=0;i<372;i++){
if(dis[i]==-1 && r[i][k]){
dis[i]=dis[k]+1;
q.push(i);
}
}
if(k==s) return 1;
}
return 0;
} int dfs(int cur,int cp){
if(cur==t) return cp; int tmp=cp,t;
for(int i=0;i<372 && tmp;i++){
if(dis[i]+1==dis[cur] && r[cur][i]){
t=dfs(i,min(r[cur][i],tmp));
r[cur][i]-=t;
r[i][cur]+=t;
tmp-=t;
}
}
return cp-tmp;
} void dinic(){
max_flow=0;
while(bfs()){
max_flow+=dfs(s,MAXINT);
}
} int main(){
int i,j,ans,cnt;
scanf("%d",&cnt);
while(cnt--){
ans=0;s=0;t=371;
memset(r,0,sizeof(r)); scanf("%d",&n);
for(i=1;i<=n;i++){
for(j=1;j<=9;j++)
scanf("%d",&rc[i][j]);
ans+=rc[i][8];
} read_graph(); //建图
dinic(); if(ans==max_flow) printf("Yes\n");
else printf("No\n");
}
return 0;
}