poj 1698 Alice's Chance(ベースネットワークフロー・構築図)

タイトル:http://poj.org/problem?id=1698
Alice's Chance
Time Limit:1000 MS
 
メモリLimit:100000 K
Total Submissions:6396
 
Acceepted:2612
Description
Alice、a charming girl、have been dreaming of being a movie star for long.Her chaces will come now、for several filmmaking companies her to Play the chief role in their films.Univerestworly、All theream theree therementYou are asked to tell her she can act in all the films.
As for a film、

it will be made ONLY on some fixed days in a week、i.e.Alice can only work for the film on these days;

Alice shoud work for it least for specified number of days;

the film Must be finished before a prearranged deadline.

For example、asuming a film can be made only on Monday、Wednesday and Saturday;Alice shoud work for the film at least for 4 days;and it must be finished within 3 weeks.In this case she can work for the film on Monday of the first week,on Mondy and Saturday of the second week,and on Monday of the third week.
Notice that on a single day Alice can work on at most ONE film.
Input
The first line of the input contains a single integer T(1==T==20)、the number of test cases.The n T cases follw.Each test case begis a singline containintegerN(1==N=20)FFFFFFthe FFFFFbererereline e e FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFberererereline e e e e e e e e e e e e e e e e e e FFFFFFFi<=7)is 1 or 0、representing whehether the the film can be made on the i-th day in a week(a week starts on Sunday):1 means that the film can be made on thisday、while 0 means the opposite.Both D(1=D=D=50 andands=thethethe fifififififififififififififififififififififififififififififififififififififififififilm===================================================W weeks.
Output
For each test case print a single line、'Yes'if Alice can ated all the films、others'No'
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

ベント

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

ソurce
POJ Monthly-2010.7.18
Aliceは映画を撮りますが、n本の映画があります.Aliceは毎週決まった数日間しか映画を撮影できないと規定しています.映画ごとにw週間撮影できます.そして、この映画はd日間撮影します.Aliceはすべての映画を撮影できるかどうかを聞きます.難点はネットワークフローシステムの構築図である.大体のパターン:

データが大きいとEKネットワークフローのアルゴリズムがよくないですね.REかMLEかを見つけました.Dinicを変えます

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N=400,INF=0x3f3f3f3f;
struct Dinic {
    int c[N][N], n, s, t, l[N], e[N];
    int flow(int maxf = INF) {
        int left = maxf;
        while (build()) left -= push(s, left);
        return maxf - left;
    }
    int push(int x, int f) {
        if (x == t) return f;
        int &y = e[x], sum = f;
        for (; y<n; y++)
            if (c[x][y] > 0 && l[x]+1==l[y]) {
                int cnt = push(y, min(sum, c[x][y]));
                c[x][y] -= cnt;
                c[y][x] += cnt;
                sum -= cnt;
                if (!sum) return f;
            }
        return f-sum;
    }
    bool build() {
        int m = 0;
        memset(l, -1, sizeof(l));
        l[e[m++]=s] = 0;
        for (int i=0; i<m; i++) for (int y=0; y<n; y++)
            if (c[e[i]][y] > 0 && l[y]<0) l[e[m++]=y] = l[e[i]] + 1;
        memset(e, 0, sizeof(e));
        return l[t] >= 0;
    }
} net;
int main()
{
    //freopen("cin.txt","r",stdin);
    int t,n,f[8],d,w;
    cin>>t;
    while(t--){
         //memset(map,0,sizeof(map));
         memset(net.c,0,sizeof(net.c));
         scanf("%d",&n);
         int i,j,k,wmax=0,dsum=0;
         for(i=1;i<=n;i++){
             for(j=1;j<=7;j++) scanf("%d",&f[j]);
             scanf("%d%d",&d,&w);
             net.c[0][i]=d;
             dsum+=d;
             wmax=max(wmax,w);
             for(j=0;j<w;j++){
                 for(k=1;k<=7;k++){  //        7  8
                      if(f[k]){   net.c[i][8+j*7+k]=1; }//map[i][n+j*7+k]=1; }
                 }
             }
         }
         int final=7*wmax+7+1;
         for(i=8;i<final;i++){
             net.c[i][final]=1;
             //map[7*i+n+j][final]=1;
         }
         net.t=final;  //  
         net.n=final+1;  //    ,   0
         int res=net.flow();
         if(res==dsum) puts("Yes");
         else puts("No");
    }
    return 0;
}