本文共 3926 字，大约阅读时间需要 13 分钟。
原题：
题目大意：
现在有一个M*N的矩阵。已知M行每行的和a[1]..a[m],N列每列的和b[1]..b[n]，以及一些限制条件：
第i行j列必须是k；第i行j列必须大于（小于)k。
试给出一种方案。
建好图，就是一个上下界流！详情 讯代码
#include #include #define ROW 205#define COL 25#define MAXE 100005#define MAXN 1250#define INF 0x7fffffffint row[ROW],col[COL];int map[ROW][COL][2];struct Edge{ int flow; int node; int next;}edge[MAXE];struct Contain{ int a,b,c; char ch;}con[1005];int cnt,head[MAXN],dep[300],ps[MAXN],ans[ROW][COL];void add( int a, int b, int flow ){ edge[cnt].flow=flow,edge[cnt].node=b,edge[cnt].next=head[a];head[a]=cnt++; edge[cnt].flow=0,edge[cnt].node=a,edge[cnt].next=head[b];head[b]=cnt++;}int fun(int x, int y, int low, int high){ map[x][y][0] = (map[x][y][0]>low)?map[x][y][0]:low; map[x][y][1] = (map[x][y][1] < col[j])?row[i]:col[j]; } scanf("%d",&N); for( i = 1; i <= N; i++ ) scanf("%d %d %c %d",&con[i].a,&con[i].b,&con[i].ch,&con[i].c); mark=1; for( mark = i = 1; (i <= N)&&mark; i++ ) { a = con[i].a; b = con[i].b; if(a&&b) { if(con[i].ch == '=') { if(!fun( a, b, con[i].c, con[i].c )) { mark = 0; continue; } } else if(con[i].ch == '>') { if(!fun( a, b, con[i].c + 1, INF )) { mark = 0; continue; } } else { if(!fun( a, b, 0, con[i].c - 1 )) { mark = 0; continue; } } } else if(a||b) { if(a){ for(j = 1; (j <= m)&&mark; j++) { b=j; if(con[i].ch == '=') { if(!fun( a, b, con[i].c, con[i].c )) { mark = 0; continue; } } else if(con[i].ch == '>') { if(!fun( a, b, con[i].c + 1, INF )) { mark = 0; continue; } } else { if(!fun( a, b, 0, con[i].c - 1 )) { mark = 0; continue; } } } } else { for(j = 1; (j <= n)&&mark; j++) { a=j; if(con[i].ch == '=') { if(!fun( a, b, con[i].c, con[i].c )) { mark = 0; continue; } } else if(con[i].ch == '>') { if(!fun( a, b, con[i].c + 1, INF )) { mark = 0; continue; } } else { if(!fun( a, b, 0, con[i].c - 1 )) { mark = 0; continue; } } } } } else { for(j = 1; (j <= n)&&mark; j++) for(k = 1; (k <= m)&&mark; k++) { a=j,b=k; if(con[i].ch == '=') { if(!fun( a, b, con[i].c, con[i].c )) { mark = 0; continue; } } else if(con[i].ch == '>') { if(!fun( a, b, con[i].c + 1, INF )) { mark = 0; continue; } } else { if(!fun( a, b, 0, con[i].c - 1 )) { mark = 0; continue; } } } } } if( mark && (sum1 == sum2) ) { memset(head,-1,sizeof(head)); cnt = 0; sum = 0; s = n + m + 2, t = n + m + 3; for(j = 1; j <= n; j++) { add( 0, j, 0); add( 0, t, row[j] ); add( s, j, row[j] ); sum += row[j]; } sum1 = s - 1; for(j = 1; j <= m; j++) { add( j+n, sum1, 0); add( j+n, t, col[j] ); add( s, sum1, col[j] ); sum += col[j]; } for(j = 1; j <= n; j++) { for(k = 1; k <= m; k++) { add( j, n+k, map[j][k][1]-map[j][k][0] ); add( j, t, map[j][k][0] ); add( s, n+k, map[j][k][0] ); sum+=map[j][k][0]; } } add( s-1, 0, INF ); if(sum==flow(s,t)) { a=n+1,b=n+k; for(j = 1; j <= n; j++) { for(k = head[j]; ~k ; k = edge[k].next) { if((edge[k].node>=a)&&(edge[k].node<=b)) ans[j][edge[k].node-n]=map[j][edge[k].node-n][0]+edge[k^1].flow; } } for(j = 1; j <= n; j++) { for(k = 1; k <= m; k++) printf("%d ",ans[j][k]); printf("\n"); } printf("\n"); } else printf("IMPOSSIBLE\n\n"); } else printf("IMPOSSIBLE\n\n"); } return 0;}
转载地址：http://nhuvi.baihongyu.com/