| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 5280 | Accepted: 2171 |
Description
Input
Output
Sample Input
2 2 0 1 0 1 0 1 0 9 3 0 1 1 1 0 0 0 6 4 2 0 1 0 1 0 1 0 9 4 0 1 1 1 0 0 0 6 2
Sample Output
Yes No
Hint
A proper schedule for the first test case: date Sun Mon Tue Wed Thu Fri Sat week1 film1 film2 film1 film1 week2 film1 film2 film1 film1 week3 film1 film2 film1 film1 week4 film2 film2 film2
2、每一天都当做一个点，然后如果这一天能演某个电影，则把该点和这个电影连一条边，边权为1；同时，把这一点和汇点连一条边，边权也为1.
3、求超级源点到汇点的最大流，若最大流等于总天数则输出Yes！！
#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
#define N 505
const int inf=10000000;
int g[N][N];
int pre[N],mark[N];
int min(int a,int b)
{
return a<b?a:b;
}
int ek(int n)
{
int i,u,ans=0;
while(1)
{
queue<int>q;
q.push(0);
memset(mark,0,sizeof(mark));
memset(pre,-1,sizeof(pre));
mark[0]=1;
while(!q.empty())
{
u=q.front();
q.pop();
for(i=0;i<=n;i++)
{
if(!mark[i]&&g[u][i])
{
mark[i]=1;
pre[i]=u;
q.push(i);
}
}
}
if(pre[n]==-1)
break;
int d=inf;
for(i=n;i!=0;i=pre[i])
{
d=min(d,g[pre[i]][i]);
}
for(i=n;i!=0;i=pre[i])
{
g[pre[i]][i]-=d;
g[i][pre[i]]+=d;
}
ans+=d;
}
//printf("%d\n",ans);
return ans;
}
int main()
{
int i,j,k,n,t,u,sum,T;
int a[22][8],d[22],w[22];
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(g,0,sizeof(g));
sum=t=0; //汇点
for(i=1;i<=n;i++)
{
for(j=0;j<7;j++)
{
scanf("%d",&a[i][j]);
}
scanf("%d%d",&d[i],&w[i]);
if(w[i]>t)
t=w[i];
}
t=t*7+n+1; //汇点的下标
for(i=1;i<=n;i++)
{
g[0][i]=d[i]; //超级源点到一般源点（电影所需天数）的边权
for(k=0;k<w[i];k++)
{
for(j=0;j<7;j++)
{
if(a[i][j])
{
u=k*7+j+n+1;
g[i][u]=g[u][t]=1;
}
}
}
sum+=d[i];
}
if(sum==ek(t))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
poj 1698 Alice's Chance(网络流),布布扣,bubuko.com
原文：http://blog.csdn.net/u011721440/article/details/38277689