求助,我已经调了一个小时的大水题了!!!
题目: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