题目链接: 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 (a
     
      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; }