学步园

题目链接:   poj 1689

题目大意:   有个人想拍n部电影，每部电影限定每周哪几天可以拍

                  并且必须在第ki周之前把这部电影拍完，问能否拍完n部电影

解题思路:  把每部电影当作一个顶点，源点指向这些顶点，容量为该电影需要拍多少天

                  然后把每一天都当作顶点，某个工作可以在这天完成就连容量为1大边

                  每天的顶点指向汇点，容量也为1

                  最后求出最大流，满流则说明可以完成这些工作

                  PS:用邻接表时要注意反向边也要加入，因为需要不断增广直到最优解

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 402
#define INF 0x3f3f3f3f
int n,m,S,E,Index,visit[MAX],flag[MAX][MAX],Map[MAX][MAX],listb[MAX];
struct snode{
    int to,c,next;
}Edge[MAX*MAX];
struct node{
    int c;
}edge[MAX][MAX];
int a[60][10],pre[MAX];

int Min(int a,int b)
{
    return (a<b)?a:b;
}

void Add_edge(int a,int b,int c)
{
    Edge[Index].c=c,Edge[Index].to=b;
    Edge[Index].next=pre[a];
    pre[a]=Index++;
}

bool BFS()
{
    int i,s,e,v;
    s=e=0;
    memset(visit,0,sizeof(visit));
    memset(flag,0,sizeof(flag));
    visit[S]=1;
    listb[s++]=S;
    while(s!=e)
    {
        v=listb[e++];
        if(v==E)
            return true;
        for(int i1=pre[v];i1!=-1;i1=Edge[i1].next)
        {
            i=Edge[i1].to;
            if(Map[v][i]&&!visit[i])
            {
                flag[v][i]=1;
                visit[i]=1;
                listb[s++]=i;
            }
        }
    }
    return false;
}

int DFS(int v,int sum)
{
    int s,t,i,to;
    s=sum;
    if(v==E||sum==0)
        return sum;
    for(i=pre[v];i!=-1;i=Edge[i].next)
    {
        to=Edge[i].to;
        if(flag[v][to])
        {
            t=DFS(to,Min(sum,Map[v][to]));
            Map[v][to]-=t;
            Map[to][v]+=t;
            sum-=t;
        }
    }
    return s-sum;
}

void Solve()
{
    while(BFS())
        DFS(S,INF);
}

int main()
{
    int i,j,Max,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        S=Max=Index=0;
        memset(edge,0,sizeof(edge));
        memset(pre,-1,sizeof(pre));
        memset(Map,0,sizeof(Map));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=9;j++)
            {
                scanf("%d",&a[i][j]);
            }
            if(a[i][9]>Max)
                Max=a[i][9];
            edge[S][i].c=a[i][8];   //前面
            Map[S][i]=a[i][8];      //前面
        }
        E=n+(Max*7)+1;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=a[i][9];j++)
            {
                for(int j1=1;j1<=7;j1++)
                {
                    if(a[i][j1]==1)
                    {
                        edge[i][n+(j-1)*7+j1].c=1;   //中间
                        Map[i][n+(j-1)*7+j1]=1;      //中间
                        edge[n+(j-1)*7+j1][E].c=1;   //后面
                        Map[n+(j-1)*7+j1][E]=1;      //后面
                    }
                }
            }
        }
        for(i=S;i<=E;i++)
        {
            for(j=S;j<=E;j++)
            {
                if(edge[i][j].c)
                {
                    Add_edge(i,j,edge[i][j].c);
                    Add_edge(j,i,-edge[i][j].c);  //不存在，但是需要用到
                }
            }
        }
        Solve();
        int pd=1;
        for(i=1;i<=n;i++)
        {
            if(Map[S][i]!=0)
            {
                pd=0;
                break;
            }
        }
        if(pd)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}