就是比较裸的一个网络流qwq
直接建源点汇点
源点连单位流量Ci 桌子连汇点流量Ri 单位桌子两两连边流量为1限流就可以了
然后输出方案就看一下流了这条边就是坐了这个桌子就吼了
#include#include #include #include #include #define inf 20021225#define maxn 100100using namespace std;struct edge{int to,lt,f;}e[maxn<<4];int in[maxn],nn,cnt=1,s,t,dep[maxn];queue que;void add(int x,int y,int f){ e[++cnt].to=y;e[cnt].lt=in[x];in[x]=cnt;e[cnt].f=f; e[++cnt].to=x;e[cnt].lt=in[y];in[y]=cnt;e[cnt].f=0;}bool bfs(){ memset(dep,0,sizeof(dep)); while(!que.empty()) que.pop(); dep[s]=1;que.push(s); while(!que.empty()) { //printf("QAQ"); int x=que.front();que.pop(); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(e[i].f&&!dep[y]) { dep[y]=dep[x]+1; if(y==t) return 1; que.push(y); } } } return dep[t]!=0;}int dfs(int x,int f){ //printf("QAQ"); if(x==t||!f) return f; int cur=f;//printf("QAQ"); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(dep[y]==dep[x]+1&&e[i].f) { int tmp=dfs(y,min(e[i].f,cur)); //if(!tmp) dep[y]=-1; e[i].f-=tmp;e[i^1].f+=tmp;cur-=tmp; if(!cur) break; } } dep[x]=-1; return f-cur;}int c[300],r[300];int dinic(){ int ans=0,w; while(bfs()) { //while(w=dfs(s,inf)) //{ ans+=dfs(s,inf); //printf("%d\n",w); //} } //printf("%d ",ans); return ans;}int main(){ int n,m,i,j,tot=0; scanf("%d%d",&m,&n); s=n+m+1;t=n+m+2;//nn=n+m+2; for(i=1;i<=m;i++) { scanf("%d",&r[i]); add(s,i,r[i]); tot+=r[i]; } for(i=1;i<=n;i++) { scanf("%d",&c[i]); add(i+m,t,c[i]); for(j=1;j<=m;j++) add(j,i+m,1); } if(dinic()==tot) { printf("1\n"); for(i=1;i<=m;i++) { for(int j=in[i];j;j=e[j].lt) { if(e[j].to==s) continue; if(!e[j].f) printf("%d ",e[j].to-m); } printf("\n"); } } else printf("0\n"); return 0;}