求助,不是萌新,不是妹子,下了c++很久
  • 板块灌水区
  • 楼主Zikl
  • 当前回复11
  • 已保存回复11
  • 发布时间2023/7/18 19:54
  • 上次更新2023/11/3 09:02:51
查看原帖
求助,不是萌新,不是妹子,下了c++很久
300166
Zikl楼主2023/7/18 19:54

求助,我已经调了一个小时的大水题了!!!

题目:P3254 圆桌问题

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define int long long
#define N 10005
using namespace std;
const int inf=1<<30;
int n,m,s,t,sum,r[N],c[N],rs;
int dep[1000005],head[1000005],net[1000005],ver[1000005],tot=1,cur[1000005],edg[1000005],maxflow;
void add(int x,int y,int z){
	ver[++tot]=y,edg[tot]=z,net[tot]=head[x],head[x]=tot;
	ver[++tot]=x,edg[tot]=0,net[tot]=head[y],head[y]=tot;
}
int bfs(){
	memset(dep,-1,sizeof(dep));
	memcpy(cur,head,sizeof(head));
	dep[s]=0;
	queue<int>q;
	q.push(s);
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=net[i]){
			int y=ver[i];
			if(dep[y]==-1&&edg[i]){
				dep[y]=dep[x]+1;
				q.push(y);
			}
		}
	}
	return dep[t]!=-1; 
}
int dfs(int u,int flow){
	if(u==t) return flow;
	int rest=flow,i,mi;
	for(i=cur[u];i&&rest;i=net[i]){
			int y=ver[i];
			if(edg[i]&&(dep[y]==dep[u]+1)){
				mi=dfs(y,min(edg[i],rest));
				if(!mi){
				dep[y]=-1;
				continue;
			}
				rest-=mi;
				edg[i]-=mi;
				edg[i^1]+=mi;
			}
		}
	cur[u]=i;
	return flow-rest;
	
}
int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>m>>n;
	s=0,t=n+m+1;
	for(int i=1;i<=m;i++){
		cin>>r[i];
		add(s,i,r[i]);
		rs+=r[i];
	}
	for(int i=1;i<=n;i++){
		cin>>c[i];
		add(i+m,t,c[i]);
	}
	for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++)
	add(i,j+m,1);
	if(dinic()==rs) cout<<"0";
	else{
		cout<<"1";
		for(int i=1;i<=m;i++){
			for(int j=head[i];j;j=net[j]){
				if(ver[j]>m&&ver[j]<=m+n&&!edg[j]) {
					cout<<ver[j]-m<<" ";
				}
			}
			cout<<endl;
		}
	}
	return 0;
} 

样例 :

4 5
4 5 3 5
3 5 2 6 4

我的输出:

0

需要的输出:

1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
2023/7/18 19:54
加载中...