Dinic求调
查看原帖
Dinic求调
876418
HHYQ_07楼主2024/3/1 22:37

评测记录,唯一通过的是输出零的。

#1 就过不去,但下载数据后看也没什么问题啊。

标准输入

3 3
2 2 2
2 2 2

标准输出

1
1 2
1 3
2 3

我的输出

1
3 1
3 2
2 1
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    char cc;
    while(1){cc=getchar();if((cc>='0'&&cc<='9')||cc=='-')break;}
    int sum=0,flag=1;
    cc=='-'?flag=-1:sum=(cc^48);
    while(1){cc=getchar();if(!(cc>='0'&&cc<='9'))break;sum=(sum<<1)+(sum<<3)+(cc^48);}
    return sum*flag;
}
inline void print(int x)
{
    if(!x)putchar('0');
    if(x<0){x=-x;putchar('-');}
    int cc[25],cntt=0;
    while(x){cc[++cntt]=x%10;x/=10;}
    for(int i=cntt;i>=1;i--)putchar(cc[i]+'0');
    putchar(' ');
}
const int N=155,M=275;
int n,m,f,tot=1,head[N+M],s,t,d[N+M],he,now[N+M];
struct node
{
	int next,to,flow;
}edge[N*M*2];
void add(int from,int to,int flow)
{
	tot++;
	edge[tot].to=to,edge[tot].flow=flow;
	edge[tot].next=head[from];
	head[from]=tot;
}
bool bfs()
{
	memset(d,0,sizeof(d));
	queue<int>q;
	q.push(s);
	d[s]=1;
	now[s]=head[s];
	while(!q.empty())
	{
		int x=q.front();q.pop();
		if(x==t)return 1;
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,flow=edge[i].flow;  
			if(!d[y]&&flow)
			{
				q.push(y);
				d[y]=d[x]+1;
				now[y]=head[y];
			}
		}
	} 
	return 0;
}
int dfs(int x,int lflow)
{
	if(x==t)return lflow;
	int rest=lflow;
	for(int i=now[x];i&&rest;i=edge[i].next)   
	{
		now[x]=i;
		int y=edge[i].to,flow=edge[i].flow;
		if(d[y]!=d[x]+1||!flow)continue;
		int k=dfs(y,min(rest,flow));
		if(!k)d[y]=0;    
		rest-=k;
		edge[i].flow-=k;       
		edge[i^1].flow+=k;
	}
	return lflow-rest; 
} 
int dinic()
{
	int maxflow=0,flow;
	while(bfs())
		while(flow=dfs(s,INT_MAX))maxflow+=flow;
	return maxflow;
}
signed main(int argc,char **argv)
{
	n=read();
	m=read();
	t=n+m+1;
	for(int i=1;i<=n;i++)
	{
		f=read();
		he+=f;
		add(s,i,f);
		add(i,s,0);
		for(int j=1;j<=m;j++)
		{
			add(i,n+j,1);
			add(n+j,i,0);
		}
	}
	for(int i=1;i<=m;i++)
	{
		f=read();
		add(i+n,t,f);
		add(t,i+n,0);
	}
	if(dinic()!=he)
	{
		print(0);
		return 0;
	}
	print(1);
    for(int x=1;x<=n;x++)
    {
    	cout<<endl;
        for(int i=head[x];i;i=edge[i].next)
	        if(edge[i].to>n&&edge[i].to!=t&&!edge[i].flow)
	            print(edge[i].to-n);
    }
	return 0;
}
2024/3/1 22:37
加载中...