POJ 1698 构图+最大流

题目大意：

　　man需要一个安排表参见演出，有n(n<=20)场，每场指定了必须表演的天数Di，和截止的周数Week_i，还指定了必须星期几表演，要求man一天最多参加一场，问能否有一个安排使得满足要求，有输出Yes，否则输出No;

分析：

　　开始自己想了个392个点的构图,后来看了题解，发现我多了一层（我拆了点，其实没有必要）……

　　源ST分别向n个场次连边（1……n），边容量为各场指定的天数Di，各场（1……n）分别作为一个节点，向指定的星期连边（注意从第一周到第Week_i的都要），容量为1（只要大于0的整数实际都可以），然后每天（n+1……n+(Week*7)）分别向汇点ED连边，容量为1;

　　求一次最大流，看maxflow是否等于sum{ Di };

　　最多372个点，果断上Edmond_Karp!

代码：

poj1698

 1 /*1698    Accepted    1328K    141MS    G++    2140B    2012-06-19 20:42:23*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 
10 #define mpair make_pair
11 #define pii pair<int,int>
12 #define MM(a,b) memset(a,b,sizeof(a));
13 typedef long long lld;
14 typedef unsigned long long u64;
15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
17 #define maxn 390
18 const int inf= 2100000000;
19 
20 int n;
21 int ST, ED;
22 int g[maxn][maxn];
23 
24 int Read(){
25     int i, j, k, t, D, W, sum= 0, week= 0;
26     scanf("%d", &n);
27     ST= 0;
28     MM( g, 0 );
29     vector<int> a;
30     for(i=1;i<=n;++i){
31         a.clear();
32         for(j=1;j<=7;++j){
33             scanf("%d", &t);
34             if( 1==t ) a.push_back( j );
35         }
36         scanf("%d%d", &D, &W);
37         g[ST][i]= D;
38         sum+= D;
39         up_max( week, W );
40         for(j=1;j<=W;++j)
41             for(k=0;k<a.size();++k)
42                 g[i][ n+(j-1)*7+a[k] ]= 1; ///!!!
43     }
44     ED= n + 7*week + 1;
45     for(i=n+1;i<=n+7*week;++i) g[i][ED]= 1;
46     return sum;
47 }
48 
49 bool vis[maxn];
50 int que[maxn], pre[maxn];
51 bool bfs(){
52     fill( vis, vis+1+ED, 0 );
53     int head= 0, tail= 0;
54     que[tail++]= ST;
55     vis[ST]= 1;
56     while( head<tail ){
57         int u= que[head++];
58         for(int v=1;v<=ED;++v){
59             if( g[u][v]>0 && !vis[v] ){
60                 pre[v]= u;
61                 if( v==ED ) return 1;
62                 que[tail++]= v;
63                 vis[v]= 1;
64             }
65         }
66     }
67     return 0;
68 }
69 
70 int Edmond_karp(){
71     int ret= 0;
72     while( bfs() ){
73         int t= inf;
74         for(int i=ED;i!=ST;i=pre[i])
75             up_min( t, g[pre[i]][i] );
76         ret+= t;
77         for(int i=ED;i!=ST;i=pre[i]){
78             g[pre[i]][i]-= t;
79             g[i][pre[i]]+= t;
80         }
81     }
82     return ret;
83 }
84 
85 int main()
86 {
87     //freopen("poj1689.in","r",stdin);
88     int Cas;
89     cin>>Cas;
90     while( Cas-- ){
91         int sum= Read();
92         int ret= Edmond_karp();
93         if( sum==ret ) puts("Yes");
94         else puts("No");
95     }
96 }

一毛原创作品，转载请注明出处。