poj 1698Alice's Chance 最大流模板題

poj 1698Alice's Chance 最大流模板題

//建立一個超級源點和一個超級匯點
//從超級源點到每一個film的權值為需要在這個film工作的天數D
//然後從film到每個星期的第j天為一條權值為1的邊
//從每個星期的第j天到超級匯點的權值為1
//這樣就可以只需要驗證從超級源點到超級匯點的最大流是否和所有film的天數之和是否相等
#include
#include
#include
#include
using namespace std;
#define maxn 1010
#define inf 0x7fffffff
struct node
{
int to;
int cap;
int next;
}edge[maxn*1000];
int nedge=0;
int head[maxn];
queue que;
int dis[maxn];
int st=0;
int en=1001;
void add(int u,int v,int cap)
{
edge[nedge].to=v;
edge[nedge].cap=cap;
edge[nedge].next=head[u];
head[u]=nedge++;
edge[nedge].to=u;
edge[nedge].cap=0;
edge[nedge].next=head[v];
head[v]=nedge++;
}
int bfs()
{
int i;
memset(dis,-1,sizeof(dis));
while(que.size())
que.pop();
dis[st]=0;
que.push(st);
while(que.size())
{
int u=que.front();
que.pop();
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]<0&&edge[i].cap>0)
{
dis[v]=dis[u]+1;
que.push(v);
}
}
}
if(dis[en]>0)
return 1;
return 0;
}
int dfs(int x,int mx)
{
if(x==en)
return mx;
int i;
int ans=0;
int a;
for(i=head[x];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v]==dis[x]+1&&edge[i].cap>0&&(a=dfs(v,min(mx,edge[i].cap))))
{
edge[i].cap-=a;
edge[i^1].cap+=a;
ans+=a;
mx-=a;
if(!mx)
break;
}
}
if(!ans)
dis[x]=-1;
return ans;
}
int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d", &T);
while(T--)
{
int N,i,j,D,W,vis[maxn],hash[maxn];
int sum = 0;
memset(head,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
nedge=0;
scanf("%d" , &N);
for(i = 1; i <= N ;i++)
{
memset(hash,0,sizeof(hash));
for(j = 1 ; j <= 7 ;j++)
{
int t;
scanf("%d", &t);
hash[j] = t;
}
scanf("%d %d" , &D ,&W);
add(st, i ,D);
sum += D;
while(W--)
{
for(j=1; j<= 7 ;j++)
if(hash[j])
{
add(i, 50+j+W*10 ,1);
if(!vis[50+j+W*10])
{
add(50+j+W*10, en ,1);
vis[50+j+W*10] = 1;
}
}
}
}
int ans = 0;
int res;
while(bfs())
while(res=dfs(0,inf))
ans+=res;
if(ans == sum)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}