poj2396
この問題の意味は簡単で、1-nのその点はn行を表し、n+1-n+m+はm列を表し、それから行列がつながって、上下界があり、ソース点s=n+m+1から各行上下界を各行値とし、各列は汇点t=n+m+2上下界を列の和とし、それから上下界ネットワークストリームでよい.
#include<cstdio>
#include<cstring>
#define maxn 10000
#define inf 1<<30
int n,m,s,t,ss,tt,nn,head[300],gap[300],dis[300],T,cnt,le[300],min[300][300],max[300][300],sum,mp[300][30];
struct Edge
{
int to,b,c,nxt;
} edge[maxn];
int MIN(int a,int b)
{
return a<b?a:b;
}
int MAX(int a,int b)
{
return a>b?a:b;
}
void clc()
{
memset(head,-1,sizeof(head));
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
memset(mp,0,sizeof(mp));
for(int i=1;i<=250;i++)
for(int j=1;j<=250;j++)
{
min[i][j]=0;
max[i][j]=inf;
}
memset(le,0,sizeof(le));
}
void ad(int x,int y,int b,int c)
{
edge[cnt].to=y;
edge[cnt].b=b;
edge[cnt].c=c;
edge[cnt].nxt=head[x];
head[x]=cnt++;
}
void add(int x,int y,int b,int c)
{
ad(x,y,b,c);
ad(y,x,0,0);
}
int build()
{
ss=nn+1,tt=ss+1;
for(int i=0;i<cnt;i++)
{
if(edge[i].c<edge[i].b)
return 1;
edge[i].c=edge[i].c-edge[i].b;
le[edge[i].to]+=edge[i].b;
le[edge[i^1].to]-=edge[i].b;
edge[i].b+=edge[i].c;
}
for(int i=1;i<=nn;i++)
{
if(le[i]>0)
add(ss,i,0,le[i]),sum+=le[i];
else
if(le[i]<0)
add(i,tt,0,-le[i]);
}
return 0;
}
int dfs(int x,int flow)
{
if(x==tt)
return flow;
int temp=flow;
int pos=tt-1;
int j;
for(j=head[x];j!=-1;j=edge[j].nxt)
{
int y=edge[j].to;
int c=edge[j].c;
if(c>0&&dis[x]==dis[y]+1)
{
int temp_flow=dfs(y,MIN(c,temp));
temp-=temp_flow;
edge[j].c-=temp_flow;
edge[j^1].c+=temp_flow;
if(temp==0||dis[0]==tt)
return flow-temp;
}
if(c>0&&pos>dis[y])
pos=dis[y];
}
if(temp==flow)
{
if(!(--gap[dis[x]]))
dis[0]=tt;
else
gap[dis[x]=pos+1]++;
}
return flow-temp;
}
int sap()
{
int maxflow=0;
gap[0]==tt;
while(dis[0]<tt)
{
maxflow+=dfs(ss,inf);
}
return sum==maxflow;
}
void print()
{
for(int i=1;i<=n;i++)
for(int j=head[i];j!=-1;j=edge[j].nxt)
{
int y=edge[j].to;
if(y<=n+m)
mp[i][y-n]=edge[j].b-edge[j].c;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
printf("%d ",mp[i][j]);
printf("%d
",mp[i][m]);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
cnt=sum=0;
scanf("%d%d",&n,&m);
s=n+m+1,t=s+1,nn=t;
clc();
for(int i=1;i<=n;i++)
{
int tp;
scanf("%d",&tp);
add(s,i,tp,tp);
}
for(int i=1;i<=m;i++)
{
int tp;
scanf("%d",&tp);
add(i+n,t,tp,tp);
}
int qipa;
scanf("%d",&qipa);
for(int i=1;i<=qipa;i++)
{
int a,b,d,aa,bb;
char c;
scanf("%d%d %c%d",&a,&b,&c,&d);
if(a==0)
{
a=1,aa=n;
}
else
aa=a;
if(b==0)
{
b=1,bb=m;
}
else
bb=b;
for(int i=a;i<=aa;i++)
for(int j=b;j<=bb;j++)
{
if(c=='=')min[i][j]=MAX(min[i][j],d),max[i][j]=MIN(max[i][j],d);
else
if(c=='>')min[i][j]=MAX(min[i][j],d+1);
else
if(c=='<')max[i][j]=MIN(max[i][j],d-1);
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
add(i,j+n,min[i][j],max[i][j]);
add(t,s,0,inf);
if(build())
{
printf("IMPOSSIBLE
");
continue;
}
if(sap())
print();
else
printf("IMPOSSIBLE
");
}
return 0;
}