家园/星际转移问题【网络流24题】

思路

　　根据题意和数据范围，很容易想到可以用网络流解决此类问题

　　如何正确的建模是此类隐式图问题的关键

　　不难发现，题中限制流量的不仅仅有船的载量，还有时间

　　时间越充沛，能转移的人数就越多

　　所以要在建图时体现时间对流量的影响

　　题中提示：每艘船的停靠站点是周期性的，此点类似牛客的一道动物森友会

　　所以考虑枚举时间来动态加边

　　首先明确给出的n个点是不包括地球月球的

　　但是在计算时我们要将地月都算成停靠的站点之一

　　所以实际上本题共有 n + 2 个站点

　　因为站点上的人数没有限制，所以每个人可以选择留下等船或者有船就上船转移

　　只要通过对时间拆点

　　建立每个站点从上一天到当天的转移路线

　　和船在站点中的转移路线

　　通过不断加边

　　转移的人数也会随之增加

　　每天结束时更新最大流

　　如果最大流 ≥ 总人数时就可以退出了

　　因为人数的上限只有50人，可以只枚举时间

　　如果人数过多的话可以考虑二分时间来跑最大流

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int inf = 0x3f3f3f3f;
 10 
 11 template<class T>inline void read(T &res)
 12 {
 13     char c;T flag=1;
 14     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 15     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 16 }
 17 
 18 namespace _buff {
 19     const size_t BUFF = 1 << 19;
 20     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 21     char getc() {
 22         if (ib == ie) {
 23             ib = ibuf;
 24             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 25         }
 26         return ib == ie ? -1 : *ib++;
 27     }
 28 }
 29 
 30 int qread() {
 31     using namespace _buff;
 32     int ret = 0;
 33     bool pos = true;
 34     char c = getc();
 35     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 36         assert(~c);
 37     }
 38     if (c == '-') {
 39         pos = false;
 40         c = getc();
 41     }
 42     for (; c >= '0' && c <= '9'; c = getc()) {
 43         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 44     }
 45     return pos ? ret : -ret;
 46 }
 47 
 48 const int maxn = 200007;
 49 
 50 int n, m;
 51 int s, t;
 52 
 53 struct edge{
 54     int from,to;
 55     LL cap,flow;
 56 };
 57 
 58 map<int, int> vis;
 59 
 60 struct DINIC {
 61     int head[maxn << 1], nxt[maxn << 1], edge[maxn << 1], cnt;
 62     int cap[maxn << 1], depth[maxn << 1];
 63 
 64     void init() {
 65         cnt = 1;
 66         memset(head, 0, sizeof(head));
 67     }
 68 
 69     void BuildGraph(int u, int v, int w) {
 70         ++cnt;
 71         edge[cnt] = v;
 72         nxt[cnt] = head[u];
 73         cap[cnt] = w;
 74         head[u] = cnt;
 75 
 76         ++cnt;
 77         edge[cnt] = u;
 78         nxt[cnt] = head[v];
 79         cap[cnt] = 0;
 80         head[v] = cnt;
 81     }
 82 
 83     queue<int> q;
 84 
 85     bool bfs() {
 86         memset(depth, 0, sizeof(depth));
 87         depth[s] = 1;
 88         q.push(s);
 89         while(!q.empty()) {
 90             int u = q.front();
 91             q.pop();
 92             for ( int i = head[u]; i; i = nxt[i] ) {
 93                 int v = edge[i];
 94                 if(depth[v]) {
 95                     continue;
 96                 }
 97                 if(cap[i]) {
 98                     depth[v] = depth[u] + 1;
 99                     q.push(v);
100                 }
101             }
102         }
103         return depth[t];
104     }
105 
106     int dfs(int u, int dist) {
107         if(u == t) {
108             return dist;
109         }
110         int flow = 0;
111         for ( int i = head[u]; i && dist; i = nxt[i] ) {
112             if(cap[i] == 0)
113                 continue;
114             int v = edge[i];
115             if(depth[v] != depth[u] + 1) {
116                 continue;
117             }
118             int res = dfs(v, min(cap[i], dist));
119             cap[i] -= res;
120             cap[i ^ 1] += res;
121             //printf("cap[%d]:%d\n",t, cap[t]);
122             dist -= res;
123             flow += res;
124         }
125         return flow;
126     }
127 
128     int maxflow() {
129         int ans = 0;
130         while(bfs()) {
131             ans += dfs(s, inf);
132         }
133         return ans;
134     }
135 } dinic;
136 
137 int table[699][100];
138 int k;
139 int r[1007];
140 int h[1007];
141 
142 int main()
143 {
144     //freopen("data.txt", "r", stdin);
145     dinic.init();
146     read(n); read(m); read(k);
147     s = 0, t = maxn;
148     n += 2;
149     for ( int i = 1; i <= m; ++i ) {
150         read(h[i]);
151         read(r[i]);
152         for ( int j = 0; j < r[i]; ++j ) {
153             read(table[i][j]);
154             table[i][j] += 2;
155         }
156     }
157     int day = 0;
158     int num = 0;
159     while(day <= 300) {
160         dinic.BuildGraph(s, n * day + 2, inf);
161         dinic.BuildGraph(n * day + 1, t, inf);
162         if(day == 0) {
163             ++day;
164             continue;
165         }
166         for ( int i = 1; i <= m; ++i ) {
167             dinic.BuildGraph(n * (day - 1) + table[i][(day - 1) % r[i]], n * day + table[i][(day) % r[i]], h[i]);
168         }
169         for ( int i = 1; i <= n; ++i ) {
170             dinic.BuildGraph(n * (day - 1) + i, n * day + i, inf);
171         }
172         num += dinic.maxflow();
173         if(num >= k) {
174             cout << day << endl;
175             return 0;
176         }
177         ++day;
178     }
179     puts("0");
180     return 0;
181 }