不想吐槽了..sample input 和sample output 完全对不上...调了一个晚上...不想说什么了...
------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,n) for(int i=0;i<n;++i)
#define clr(x,c) memset(x,c,sizeof(x))
#define Rep(i,l,r) for(int i=l;i<r;++i)
#define REP(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int maxn=50;
const int inf=0x7fffffff;
int a[maxn],b[maxn];
int ans[maxn][maxn];
struct Edge {
int from,to,cap,flow;
Edge(int u,int v,int c,int f):
from(u),to(v),cap(c),flow(f) {}
};
struct ISAP {
bool vis[maxn];
int d[maxn];
int cur[maxn];
int num[maxn];
int p[maxn];
int n,s,t;
vector<int> g[maxn];
vector<Edge> edges;
void init(int n) {
this->n=n;
rep(i,n) g[i].clear();
edges.clear();
}
void bfs() {
clr(vis,0);
queue<int> q;
d[t]=0; vis[t]=1; q.push(t);
while(!q.empty()) {
int x=q.front(); q.pop();
rep(i,g[x].size()) {
Edge &e=edges[g[x][i]^1];
if(!vis[e.from] && e.cap>e.flow) {
d[e.from]=d[x]+1;
vis[e.from]=1;
q.push(e.from);
}
}
}
}
void addEdge(int from,int to,int cap) {
edges.push_back( Edge(from,to,cap,0) );
edges.push_back( Edge(to,from,0,0) );
g[from].push_back(edges.size()-2);
g[to].push_back(edges.size()-1);
}
int augment() {
int a=inf,x=t;
while(x!=s) {
Edge &e=edges[p[x]];
a=min(a,e.cap-e.flow);
x=e.from;
}
x=t;
while(x!=s) {
edges[p[x]].flow+=a;
edges[p[x]^1].flow-=a;
x=edges[p[x]].from;
}
return a;
}
int maxFlow(int s,int t) {
this->s=s; this->t=t;
clr(num,0); clr(cur,0);
bfs(); rep(i,n) num[d[i]]++;
int flow=0,x=s;
while(d[s]<n) {
if(x==t) {
flow+=augment();
x=s;
}
int ok=0;
Rep(i,cur[x],g[x].size()) {
Edge &e=edges[g[x][i]];
if(e.cap>e.flow && d[e.to]+1==d[x]) {
ok=1;
p[e.to]=g[x][i];
cur[x]=i;
x=e.to;
break;
}
}
if(!ok) {
int m=n-1;
rep(i,g[x].size()) {
Edge &e=edges[g[x][i]];
if(e.cap>e.flow) m=min(m,d[e.to]);
}
if(--num[d[x]]==0) break;
num[d[x]=m+1]++;
cur[x]=0;
if(x!=s) x=edges[p[x]].from;
}
}
return flow;
}
void getAns(int r,int c) {
REP(i,1,r) {
rep(j,g[i].size()) {
Edge &e=edges[g[i][j]];
if(e.to!=0) ans[i][e.to-r]=e.flow+1;
}
}
}
} S;
int main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
int CASE;
scanf("%d",&CASE);
Rep(kase,1,CASE+1) {
printf("Matrix %d\n",kase);
int r,c;
scanf("%d%d",&r,&c);
S.init(r+c+2);
a[0]=0; b[0]=0;
REP(i,1,r) scanf("%d",&a[i]);
REP(i,1,c) scanf("%d",&b[i]);
REP(i,1,r) S.addEdge(0,i,a[i]-a[i-1]-c);
REP(i,1,c) S.addEdge(i+r,r+c+1,b[i]-b[i-1]-r);
REP(i,1,r) REP(j,1,c) S.addEdge(i,j+r,19);
S.maxFlow(0,r+c+1);
S.getAns(r,c);
REP(i,1,r) {
REP(j,1,c) printf("%d ",ans[i][j]);
printf("\n");
}
printf("\n");
}
return 0;
}
------------------------------------------------------------------------------
Problem I
Matrix Decompressing
Input: Standard Input
Output: Standard Output
Some RxC matrix of positive integers is encoded and represented by its R cumulative row sum and C column sum entries. Given, R, C and those R+C cumulative row sum and column sums, you want to decode the matrix (i.e., find all the individual R*C entries).
Here,
Or in other words, the i-th row sum is the sum of all the entries in rowi. And the cumulative i-th row sum is the sum of all the row sums from row 1 to row i (inclusive).
Input
There can be multiple test cases. The first line of input contains the number of test cases, T (1 ≤T ≤ 100). Each test case contains 3 lines of input. The first line of the test case gives the size of the matrix: the number of rows, R (1 ≤ R ≤ 20) and the number of columns C (1 ≤ C ≤20). The next line contains all the R cumulative row sums, and the last line of the test case contains the C cumulative column sums. Any two successive numbers in the same line is separated by a single space.
Output
For each test case print the label of the test case in the first line. The format of this label should be “Matrix x” where x would be replaced by the serial number of the test case starting at 1. In each of the following R lines print C integers giving all the individual entries of the matrix. You can assume that there is at least one solution for each of the given encodings. To simplify the problem further, we add the constraint that each entry in the matrix must be an integer between 1 and 20. In case of multiple solutions, you can output any one of them.
Sample Input Output for Sample Input
|
2
3 4
10 31 58
10 20 37 58
3 4
10 31 58
10 20 37 58
|
Matrix 1
1 6 1 2
1 2 2 16
8 2 14 3
Matrix 2
1 11 7
1 1 7 12
8 8 9 2
|