评测记录,唯一通过的是输出零的。
#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;
}