样例re求调
  • 板块P3254 圆桌问题
  • 楼主xrxtcl
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/7 23:07
  • 上次更新2023/11/2 22:23:13
查看原帖
样例re求调
663912
xrxtcl楼主2023/9/7 23:07
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010;
struct lsqxx{
	int t, val, nxt, cap; 
}e[N << 4]; 
int n, m, s, t, cnt = 1;
int num[N], cur[N], dep[N];
void addedge(int f, int t, int c){
	e[++cnt].cap = c;
	e[cnt].nxt = num[f];
	e[cnt].t = t;
	e[cnt].val = c;
	num[f] = cnt;
	e[++cnt].cap = 0;
	e[cnt].nxt = num[t];
	e[cnt].t = f;
	e[cnt].val = 0;
	num[t] = cnt;
}

bool bfs(){
	queue<int>q;
	for(int i = 1 ; i <= n ; i ++)
		dep[i] = -1;
	q.push(s);
	dep[s] = 0;
	while(!q.empty()){
		int p = q.front();
		q.pop();
		for(int i = num[p] ; i ; i = e[i].nxt)
			if(e[i].val && dep[e[i].t] == -1)
				dep[e[i].t] = dep[p] + 1, q.push(e[i].t);
	}
	return dep[t] != -1;
}
int dfs(int p, int mc){
	if(p == t) return mc;
//	cout << p << ' ';
	int now = mc;
	for(int i = num[p] ; i ; i = e[i].nxt){
		if(e[i].val && dep[e[i].t] == dep[p] + 1){
			int flow = dfs(e[i].t, min(mc, e[i].val));
			if(!flow)dep[e[i].t] = -1;
			e[i ^ 1].val += flow;
			e[i].val -= flow;
			mc -= flow;
		}
	} 
	return now - mc;
}
int r[N], c[N];
int init(){
	int ret = 0;
	cin >> n >> m;
	s = 1, t = 2 + m + n;
	for(int i = 1 ; i <= n ; i ++)
		cin >> r[i], addedge(s, i + 1, r[i]), ret += r[i];
	for(int i = 1 ; i <= m ; i ++)
		cin >> c[i], addedge(i + n + 1, t, c[i]);
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 1 ; j <= m ;j ++)
			addedge(i + 1, j + n + 1, 1);
	return ret;
} 
signed main(){
	int k = init();
	int ans = 0;
	while(bfs())ans += dfs(s, LLONG_MAX);
	if(ans != k){
		cout << 0 << '\n';
		return 0;
	} 
	cout << 1 << '\n';
	for(int i = 1 ; i <= n ; i ++, cout << '\n')
		for(int j = num[i] ; j ; j =e[j].nxt)
			if(e[j].cap >= e[j].val)
				cout << e[j].t << ' ';
	return 0;
}

2023/9/7 23:07
加载中...