2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N = 110; typedef long long LL; struct edge { LL x,cap,rev; }; vector<edge> e[N]; int n,m,s,t; int d[N],it[N]; void add(int a,int b,LL c) { e[a].push_back({b,c,(LL)e[b].size()}); e[b].push_back({a,0,(LL)e[a].size() - 1}); } void bfs() { memset(d,-1,sizeof d); queue<int> q; d[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(auto t : e[u]) if(t.cap > 0 && d[t.x] < 0) d[t.x] = d[u] + 1,q.push(t.x); } } LL dfs(int u,LL f) { if(u == t) return f; for(int &i = it[u]; i < e[u].size(); i ++) { edge &t = e[u][i]; if(d[u] < d[t.x] && t.cap > 0) { LL d = dfs(t.x,min(f,t.cap)); if(d > 0) { t.cap -= d; e[t.x][t.rev].cap += d; return d; } } } return 0; } LL dinic() { LL flow = 0; while(1) { bfs(); if(d[t] < 0) break; memset(it,0,sizeof it); LL d = dfs(s,1e18); while(d > 0) { flow += d; d = dfs(s,1e18); } } return flow; } int main() { cin>>m>>n; s = 0,t = n + m + 1; LL res = 0; string str; for(int i = 1,x,y; i <= m; i ++) { cin>>x; add(s,i,x); res += x; getline(cin,str); stringstream ss(str); while(ss>>y) add(i,y + m,1e18); } for(int i = 1,x; i <= n; i ++) cin>>x,add(i + m,t,x); res -= dinic(); for(int i = 1; i <= m; i ++) if(d[i] >= 0) cout<<i<<' '; cout<<'\n'; for(int i = 1; i <= n; i ++) if(d[i + m] >= 0) cout<<i<<' '; cout<<'\n'; cout<<res<<endl; return 0; }
- 1
信息
- ID
- 972
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 26
- 已通过
- 7
- 上传者
