显示代码纯文本
#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 100;
const int inf = 1e7;
const int maxd = 50;
const int deep = 40;
int flyer[maxn][maxn];
int cap[maxn];
int res;
int cnt;
int n, m, k, s, t;
class solve_flow {
private:
struct edge {
int to, le, ne;
edge(){}
edge(int a, int b, int c) { to = a, le = b, ne = c;}
}e[maxn*maxn*maxn];
int head[maxn*maxn], tot;
int cur[maxn*maxn];
int de[maxn*maxn];
public:
void add_edge(int a, int b, int c) {
++tot; e[tot] = edge(b, c, head[a]);
head[a] = tot;
++tot; e[tot] = edge(a, 0, head[b]);
head[b] = tot;
}
bool bfs() {
queue<int> q;
while(!q.empty()) q.pop();
memset(de, 0, (t+1)<<2);
memcpy(cur, head, (t+1)<<2);
q.push(s);
de[s] = 1;
while(!q.empty()) {
int now = q.front(); q.pop();
if(now == t) return true;
for(int i = head[now]; i; i = e[i].ne) {
int to = e[i].to;
if(de[to] || e[i].le <= 0) continue;
de[to] = de[now]+1;
q.push(to);
}
}
return de[t];
}
int dfs(int now, int min_flow) {
if(now == t) return min_flow;
int now_flow;
for(int &i = cur[now]; i; i = e[i].ne) {
int to = e[i].to;
if(de[to] != de[now]+1 || e[i].le <= 0) continue;
now_flow = dfs(to, min(min_flow, e[i].le));
if(now_flow == 0) continue;
e[i].le -= now_flow;
if(i & 1) e[i+1].le += now_flow;
else e[i-1].le += now_flow;
return now_flow;
}
return 0;
}
int dinic() {
int orz = 0, tmp, ans;
while(bfs())
while(tmp = dfs(s, inf)){
orz += tmp;
ans = tmp;
}
return orz;
}
}sf;
int mod(int a, int b) {
if(a % b) return a % b;
return b;
}
bool check() {
for(int i = 1; i <= m; i++) {
int now = flyer[i][mod(res, flyer[i][0])];//这一天飞船在的站
int ne = flyer[i][mod(res+1, flyer[i][0])];//下一个到达的站
if(now == 0) now = m*maxd+res;
else if(now == -1) now = (m+1)*maxd+res;
else now = (now-1)*maxd+res;
if(ne == 0) ne = m*maxd+res+1;
else if(ne == -1) ne = (m+1)*maxd+res+1;
else ne = (ne-1)*maxd+res+1;
sf.add_edge(now, ne, cap[i]);//这个站的当前天到下一个站下一天
// sf.add_edge(now, now+1, inf);//滞留不动
}
for(int i = 1; i <= m+2; i++) {
sf.add_edge((i-1)*maxd+res, (i-1)*maxd+res+1, inf);
}
sf.add_edge((m+1)*maxd+res+1, t, inf);//当前
cnt += sf.dinic();
if(cnt == k) return true;
else return false;
}
//(m*max)
int solve() {
s = (m+5)*100+1;
t = s+1;
res = 0;
sf.add_edge(s, m*maxd+1, k);
while(true) {
++res;
if(check()) return res;
if(res >= deep) return 0;
}
}
void read() {
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= m; i++) {
scanf("%d %d", &cap[i], &flyer[i][0]);
for(int j = 1; j <= flyer[i][0]; j++) {
scanf("%d", &flyer[i][j]);
}
}
}
int main() {
freopen("home.in", "r", stdin);
freopen("home.out", "w", stdout);
read();
printf("%d\n", solve());
return 0;
}
Fmuckss