Redraw Beautiful Drawings
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 4302 Accepted Submission(s): 1282
Problem Description
Alice and Bob are playing together. Alice is crazy about art and she has visited many museums around the world. She has a good memory and she can remember all drawings she has seen.
Today Alice designs a game using these drawings in her memory. First, she matches K+1 colors appears in the picture to K+1 different integers(from 0 to K). After that, she slices the drawing into grids and there are N rows and M columns. Each grid has an integer on it(from 0 to K) representing the color on the corresponding position in the original drawing. Alice wants to share the wonderful drawings with Bob and she tells Bob the size of the drawing, the number of different colors, and the sum of integers on each row and each column. Bob has to redraw the drawing with Alice's information. Unfortunately, somtimes, the information Alice offers is wrong because of Alice's poor math. And sometimes, Bob can work out multiple different drawings using the information Alice provides. Bob gets confused and he needs your help. You have to tell Bob if Alice's information is right and if her information is right you should also tell Bob whether he can get a unique drawing.
Today Alice designs a game using these drawings in her memory. First, she matches K+1 colors appears in the picture to K+1 different integers(from 0 to K). After that, she slices the drawing into grids and there are N rows and M columns. Each grid has an integer on it(from 0 to K) representing the color on the corresponding position in the original drawing. Alice wants to share the wonderful drawings with Bob and she tells Bob the size of the drawing, the number of different colors, and the sum of integers on each row and each column. Bob has to redraw the drawing with Alice's information. Unfortunately, somtimes, the information Alice offers is wrong because of Alice's poor math. And sometimes, Bob can work out multiple different drawings using the information Alice provides. Bob gets confused and he needs your help. You have to tell Bob if Alice's information is right and if her information is right you should also tell Bob whether he can get a unique drawing.
Input
The input contains mutiple testcases.
For each testcase, the first line contains three integers N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400) and K(1 ≤ K ≤ 40).
N integers are given in the second line representing the sum of N rows.
M integers are given in the third line representing the sum of M columns.
The input is terminated by EOF.
For each testcase, the first line contains three integers N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400) and K(1 ≤ K ≤ 40).
N integers are given in the second line representing the sum of N rows.
M integers are given in the third line representing the sum of M columns.
The input is terminated by EOF.
Output
For each testcase, if there is no solution for Bob, output "Impossible" in one line(without the quotation mark); if there is only one solution for Bob, output "Unique" in one line(without the quotation mark) and output an N * M matrix in the following N lines representing Bob's unique solution; if there are many ways for Bob to redraw the drawing, output "Not Unique" in one line(without the quotation mark).
Sample Input
2 2 4 4 2 4 2 4 2 2 2 2 5 0 5 4 1 4 3 9 1 2 3 3
Sample Output
Not Unique Impossible Unique 1 2 3 3
Author
Fudan University
Source
开始要做这个题的时候，我是拒绝的，因为只比hdu4975A simple Gaussian elimination problem.【网络流判断是否解唯一】 多了一个输出，而输出的边的序号可以从建边时候看出来，so easy 啊有木有，然而图样图森破啊，4975的数据多，但是弱，4888数据量小，但是情况多。
由于4888的数据量小，我们可以不用删边。根据本题的特点，二分图加了源点汇点，我们理解了4975中存在一圈正环=>多解，但是这么特殊的图，两侧连着S,T必须是满流，那么只能是中间部分存在流量可以流动的情况，本题中采取的方法是判断从左侧某一点到右侧某两个点，若都在(0,k)范围内，说明可以流动
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=400005;
const int mn=100005;
const int oo=0x3f3f3f3f;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c1,int c2)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<=node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
///====================
int n,m,k,cas=1;
int num[550][550];
bool judge()
{
bool dou[500][500];
memset(dou,0,sizeof(dou));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int z=j+1;z<=m;z++)
{
bool f1=0,f2=0;
if(num[i][j]>0&&num[i][z]<k)
{
if(dou[z][j])return 0;
f1=1;
}
if(num[i][z]>0&&num[i][j]<k)
{
if(dou[j][z])return 0;
f2=1;
}
if(f1)dou[j][z]=1;
if(f2)dou[z][j]=1;
}
}
}
return 1;
}
///====================
int main()
{
//freopen("cin.txt","r",stdin);
//scanf("%d",&t);
while(~scanf("%d%d%d",&n,&m,&k))
{
prepare(n+m+2,0,n+m+1);
int sum=0;
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
sum+=a;
addedge(0,i,a,0);
}
int sum1=0;
for(int i=1+n;i<=n+m;i++)
{
int a;
scanf("%d",&a);
sum1+=a;
addedge(i,n+m+1,a,0);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=n+m;j++)
addedge(i,j,k,0);
int total=Dinic_flow();
for(int i=1;i<=n;i++)
{
//printf("head=%d\n",head[i]);
for(int j=head[i];j!=-1;j=nxt[j])
{
// printf("reach=%d ",reach[j]);
if(reach[j]<=n+m&&reach[j]>n)
{
num[i][reach[j]-n]=k-flow[j];
// printf("flow=%d ",k-flow[j]);
// printf("i=%d,j=%d,num=%d\n",i,j,num[i][reach[j]-n]);
}
// puts("");
}
}
if(sum!=total||sum1!=total)
printf("Impossible\n");
else if(!judge())
printf("Not Unique\n");
else
{
printf("Unique\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>1)printf(" ");
printf("%d",flow[(i-1)*2*m+2*j-1+2*n+2*m]);
}
puts("");
}
}
}
return 0;
}刚刚的方法有点投机取巧，放到4975只能输入输出开挂+ISAP才能过，事实上，4975的代码之所以拿到4888过不了，才不是我最开始输出边不是用链式前向星而用序号错的呢，╭(╯^╰)╮
当我根据链式前向星判环的时候一定是会遇到pre==v的，4975的处理方法是直接continue了，然而怎么可以？pre==v的时候只不过是恰好找到了前一个点你凭啥不给biu赋值？不给biu赋值，你下一步删边那玩意能准么
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=400005;
const int mn=100005;
const int oo=0x3f3f3f3f;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c1,int c2)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<=node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
///====================
int n,m,k,cas=1;
int mark[mn];
bool dfs(int u,int pre)
{
int biu=-1;
mark[u]=true;
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=reach[i];
if(pre==v)
{
biu=i;//这句话必须加，不加4975可以做 4888做不了
continue;
}
if(flow[i]>0)
{
if(mark[v])return true;
if(dfs(v,u))return true;
}
if(biu==-1) head[u]=nxt[i];
else nxt[biu]=nxt[i];
biu=i;
}
mark[u]=false;
return false;
}
bool judge()
{
memset(mark,false,sizeof(mark));
for(int i=0;i<node;i++)
if(dfs(i,-1))return true;
return false;
}
///====================
int main()
{
// freopen("cin.txt","r",stdin);
//scanf("%d",&t);
while(~scanf("%d%d%d",&n,&m,&k))
{
prepare(n+m+2,0,n+m+1);
int sum=0;
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
sum+=a;
addedge(0,i,a,0);
}
int sum1=0;
for(int i=1+n;i<=n+m;i++)
{
int a;
scanf("%d",&a);
sum1+=a;
addedge(i,n+m+1,a,0);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=n+m;j++)
addedge(i,j,k,0);
int total=Dinic_flow();
if(sum!=total||sum1!=total)
printf("Impossible\n");
else if(judge())
printf("Not Unique\n");
else
{
printf("Unique\n");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>1)printf(" ");
printf("%d",flow[(i-1)*2*m+2*j-1+2*n+2*m]);
}
puts("");
}
}
}
return 0;
}
京公网安备 11010502036488号