POJ1149 网络流最大流

POJ1149 网络流最大流

#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1010;
struct node{int v, w, nxt;
}edge[N * N];
int s[N], fir[N], deep[N], vis[N];
int n, m, k, cnt, st, ed;
inline void add(int u, int v, int w){edge[++cnt] = (node){v, w, fir[u]}; fir[u] = cnt;edge[++cnt] = (node){u, 0, fir[v]}; fir[v] = cnt;
}
inline int bfs(){memset(deep, 0, sizeof(deep));deep[st] = 1;queue<int> q;q.push(st);while(!q.empty()){int u = q.front();q.pop();for(int i = fir[u]; i; i = edge[i].nxt){int v = edge[i].v;if(edge[i].w && !deep[v]){deep[v] = deep[u] + 1;q.push(v);}}}return deep[ed];
}
inline int dfs(int u, int fl){if(u == ed || fl == 0) return fl;int f = 0;for(int i = fir[u]; i; i = edge[i].nxt){int v = edge[i].v;if(edge[i].w && deep[u] + 1 == deep[v]){int x = dfs(v, min(fl, edge[i].w));edge[i].w -= x;edge[i^1].w += x;fl -= x;f += x;}}if(!f) deep[u] = -2;return f;
}
inline int Dinic(){int ans = 0, d;while(bfs()){while((d = dfs(st, 0x3f3f3f3f))){ans += d;}}return ans;
}
int main(){
#ifdef ONLINE_JUDGE
#elsefreopen("in.txt", "r", stdin);
#endif //ONLINE_JUDGEint a, b, c;while(~scanf("%d%d", &m, &n)){cnt = 1;st = 0, ed = n + 1;memset(fir, 0, sizeof(fir));memset(vis, 0, sizeof(vis));for(int i = 1; i <= m; i++){scanf("%d", &s[i]);}for(int i = 1; i <= n; i++){scanf("%d", &k);b = 0;for(int j = 1; j <= k; j++){scanf("%d", &a);if(!vis[a]) b += s[a];else add(vis[a], i, 0x3f3f3f3f);vis[a] = i;}add(st, i, b);scanf("%d", &c);add(i, ed, c);}int ans = Dinic();printf("%d\n", ans);}return 0;
}