神奇的上下界网络流----- （总结by ： becauseofyou）(二)
u=pre[u];
}
return maxflow;
}
int m , n , S, T;
int sum_row[210] , sum_col[210];
int low[210][210] , up[210][210] ,in[10010];
bool judge(int i,int j,char op,int c)
{
if(op=='=')
{
if(c >= low[i][j] && c <= up[i][j])
{
low[i][j] = c;
up[i][j] = c;
}
else return false;
}
else if(op=='>')
{
low[i][j] = max(low[i][j],c+1);
if(low[i][j] > up[i][j]) return false;
}
else
{
up[i][j] = min(up[i][j],c-1);
if(low[i][j] > up[i][j]) return false;
}
return true;
}
bool init()
{
E=0;
memset(head,-1,sizeof(head));
memset(in,0,sizeof(in));
int i , j , k , a, b , c;
scanf("%d%d",&m,&n);
int tot = 2 * n * m;
S = 0; T = tot + n + m + 1;
for(i = 1; i <= m; i++)
{
scanf("%d",&sum_row[i]);
in[i+tot] = sum_row[i];
in[S] -= sum_row[i];
//add_edge(S,i+tot,sum_row[i],0);
}
for(i = 1; i <= n; i++)
{
scanf("%d",&sum_col[i]);
in[T] += sum_col[i];
in[m+tot+i] = - sum_col[i];
//add_edge(m+tot+i,T,sum_col[i],0);
}
add_edge(T,S,INF,0);
scanf("%d",&k); char op[5];
for(i = 1; i <= m; i++) for(j = 1; j <= n; j++) low[i][j] = 0, up[i][j] = 200000;
bool flag = true;
for(int x = 0; x < k; x++)
{
scanf("%d%d%s%d",&a,&b,op,&c);
if(!a)
{
if(!b)
{
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
if(!judge(i,j,op[0],c)) flag = false;
}
}
}
else
{
for(i = 1; i <= m; i++)
{
if(!judge(i,b,op[0],c)) flag = false;
}
}
}
{
if(!b)
{
for(i = 1; i <= n; i++)
{
if(!judge(a,i,op[0],c)) flag = false;
}
}
else
{
if(!judge(a,b,op[0],c)) flag = false;
}
}
}
/* for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
printf("i = %d j = %d %d %d \n",i , j , low[i][j],up[i][j] );
}
}
*/
return flag;
}
int ID(int i,int j)
{
return (i-1)*n+j;
}
int ans[250][250];
bool check()
{
for(int i = 1; i <= m; i++)
{
int s = 0;
for(int j =1; j <=n;j ++)
{
s += ans[i][j];
}
if(s!=sum_row[i]) return false;
}
for(int i = 1; i <= n; i++)
{
int s = 0;
for(int j = 1; j <= m; j++)
{
s += ans[j][i];
}
if(s!=sum_col[i]) return false;
}
return true;
}
bool solve()
{
int i , j , k;
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
int c = up[i][j] - low[i][j];
int id = ID(i,j);
// printf("i=%d j=%d id = %d %d c = %d\n",i,j,id,id+n*m,c);
add_edge(id,id+n*m,c,0);
in[id] -= low[i][j];
in[id+n*m] += low[i][j];
}
}
int ss = T + 1, tt = ss + 1;
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
add_edge(2*n*m+i,ID(i,j),200000,0);
}
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{ //printf("%d %d\n",2*n*m+m+i,ID(j,i)+n*m);
add_edge(ID(j,i)+m*n,2*m*n+m+i,200000,0);
}
}
for(i = 0; i <= 2*m*n+m+n+1 ; i++)
{
//printf("in[%d]=%d\n",i,in[i])