rt 输入
3 3
2 2 2
2 2 2
要求输出
1
1 2
1 3
2 3
我的输出
1
1 3
2 3
1 2
wa了 程序,如下
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int head[500],cur[500],lv[500],qqt[500],cont=1,start,end,ns,tt,n;
struct li {
int to,next,w;
} e[85000];
void add(int s,int t,int w) {
e[++cont].to=t;
e[cont].w=w;
e[cont].next=head[s];
head[s]=cont;
e[++cont].to=s;
e[cont].w=0;
e[cont].next=head[t];
head[t]=cont;
return;
}
bool bfs() {
for(int i=1; i<=n; ++i)cur[i]=head[i],lv[i]=-1;
lv[start]=0;
queue<int>q;
q.push(start);
int th,ak,vk;
while(!q.empty()) {
th=q.front();
q.pop();
if(th==end)break;
for(int i=head[th]; i; i=e[i].next) {
ak=e[i].to,vk=e[i].w;
if(lv[ak]==-1&&vk>0) {
lv[ak]=lv[th]+1;
q.push(ak);
}
}
}
return lv[end]!=-1;
}
int dfs(int a,int flow) {
if(a==end)return flow;
int ak,vk,c,rnm=flow;
for(int i=cur[a]; i&&rnm; i=e[i].next) {
cur[a]=i;
ak=e[i].to,vk=e[i].w;
if(vk>0&&lv[ak]==lv[a]+1) {
c=dfs(ak,min(rnm,vk));
rnm-=c;
e[i].w-=c;
e[i^1].w+=c;
}
}
return flow-rnm;
}
int dinic() {
int ans;
while(bfs())ans+=dfs(start,11451419);
return ans;
}
int main() {
scanf("%d%d",&ns,&tt);
n=ns+tt;
start=n+1,end=n+2;
int ls,lss,wkk=0;
for(int i=1; i<=ns; i++) {
scanf("%d",&ls);
wkk+=ls;
add(start,i,ls);
}
for(int i=1; i<=tt; i++) {
scanf("%d",&ls);
add(i+ns,end,ls);
}
for(int i=1; i<=ns; i++) {
for(int j=1; j<=tt; j++)
add(i,ns+j,1);
}
n=n+2;
// for(int i=1; i<=ns; i++) {
// for(int j=head[i]; j; j=e[j].next) {
// if(e[j].w==1)printf("%d ",e[j].to-ns);
// }
// printf("\n");
// }
if(dinic()!=wkk) {
printf("0");
return 0;
}
printf("1\n");
ls=0;
for(int i=1; i<=ns; i++) {
for(int j=head[i]; j; j=e[j].next) {
if(e[j].to<=ns+tt&&e[j].w==0)qqt[++ls]=e[j].to-ns;
//printf("%d ",e[j].to-ns);
}
sort(qqt+1,qqt+1+ls);
for(int j=1; j<=ls; j++) {
printf("%d ",qqt[j]);
}
ls=0;
printf("\n");
}
}