1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N = 510; 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>>n>>m; s = 0,t = n + m + 1; LL sum = 0; for(int i = 1,x; i <= n; i ++) cin>>x,add(i + m,t,x),sum += x; for(int i = 1,x; i <= m; i ++) cin>>x,add(s,i,x); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) add(j,i + m,1); LL res = dinic(); if(res != sum) { cout<<0<<endl; return 0; } cout<<1<<endl; for(int i = 1; i <= n; i ++) { for(auto x : e[i + m]) if(x.cap) cout<<x.x<<' '; cout<<'\n'; } return 0; }
- 1
信息
- ID
- 964
- 时间
- 5000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 6
- 已通过
- 5
- 上传者