题意：有N部电影，分别可以在一个星期的几天拍摄，并可以拍W个星期，Alice可以有D个星期拍这部电影，一天只能拍一部电影。问Alice能否拍完所有电影。
拆点。求匹配。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 6 using namespace std; 7 const int maxn = 1055; 8 const int maxm = 555; 9 int g[maxn][maxm]; 10 int nx,ny; 11 bool vis[maxm]; 12 int linky[maxm]; 13 14 bool dfs(int x) 15 { 16 for (int y = 1; y <= ny; ++ y) 17 { 18 if(!vis[y] && g[x][y]) 19 { 20 vis[y] = 1; 21 if(linky[y] == -1 || dfs(linky[y])) 22 { 23 linky[y] = x; 24 return true; 25 } 26 } 27 } 28 return false; 29 } 30 31 int maxmatch() 32 { 33 memset(linky,-1,sizeof(linky)); 34 for (int x = 1; x <= nx; ++ x) 35 { 36 memset(vis, 0, sizeof(vis)); 37 if (!dfs(x)) 38 return false; 39 } 40 return true; 41 } 42 int main() 43 { 44 int t, n; 45 //freopen("a.txt","r",stdin); 46 scanf("%d", &t); 47 int a[9]; 48 while (t--) 49 { 50 scanf("%d", &n); 51 memset(g, 0, sizeof(g)); 52 nx = ny = 0; 53 while (n--) 54 { 55 for (int i = 0; i < 9; ++i) 56 scanf("%d",&a[i]); 57 if (a[8] > ny) ny = a[8]; 58 for (int i = 0; i < a[7]; ++i) 59 { 60 ++nx; 61 for (int j = 0; j < 7; ++j) 62 { 63 if (a[j]) 64 { 65 for (int k = 0; k < a[8]; ++k) 66 g[nx][k * 7 + j + 1] = 1; 67 } 68 } 69 } 70 } 71 ny *= 7; 72 if (maxmatch()) puts("Yes"); 73 else puts("No"); 74 } 75 return 0; 76 }