poj 1698 Alice's Chance (最大流Dinic)

題目鏈接: poj 1689

題目大意: 有個人想拍n部電影，每部電影限定每周哪幾天可以拍

並且必須在第ki周之前把這部電影拍完，問能否拍完n部電影

解題思路: 把每部電影當作一個頂點，源點指向這些頂點，容量為該電影需要拍多少天

然後把每一天都當作頂點，某個工作可以在這天完成就連容量為1大邊

每天的頂點指向匯點，容量也為1

最後求出最大流，滿流則說明可以完成這些工作

PS:用鄰接表時要注意反向邊也要加入，因為需要不斷大增廣直到最優解

代碼:

#include 
#include 
#include 
#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 (aMax)
                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;
}