A simple Gaussian elimination problem.

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 561 Accepted Submission(s): 185

Problem Description

Dragon is studying math. One day, he drew a table with several rows and columns, randomly wrote numbers on each elements of the table. Then he counted the sum of each row and column. Since he thought the map will be useless after he got the sums, he destroyed the table after that.However Dragon’s mom came back and found what he had done. She would give dragon a feast if Dragon could reconstruct the table, otherwise keep Dragon hungry. Dragon is so young and so simple so that the original numbers in the table are one-digit number (e.g. 0-9). Could you help Dragon to do that?

Input

The first line of input contains only one integer, T(<=30), the number of test cases. Following T blocks, each block describes one test case.There are three lines for each block. The first line contains two integers N(<=500) and M(<=500), showing the number of rows and columns. The second line contains N integer show the sum of each row. The third line contains M integer show the sum of each column.

Output

Each output should occupy one line. Each line should start with “Case #i: “, with i implying the case number. For each case, if we cannot get the original table, just output: “So naive!”, else if we can reconstruct the table by more than one ways, you should output one line contains only: “So young!”, otherwise (only one way to reconstruct the table) you should output: “So simple!”.

Sample Input

3 1 1 5 5 2 2 0 10 0 10 2 2 2 2 2 2

Sample Output

Case #1: So simple! Case #2: So naive! Case #3: So young!

Source

2014 Multi-University Training Contest 10

但是找环。发现标程竟然是错的。

1
3 2
18
9
3
15
15

暴力搜找环会TLE。 这题可以和HDU 4888 互为参考下。   一种找环比较正确，而且快速的方法：和Tarjan的思路差不多。 就是从汇点开始去dfs,  记录哪些点是回不到end的。 然后就一遍dfs就可以解决了。

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

const int MAXN = 2010;//点数的最大值
const int MAXM = 1200010;//边数的最大值
const int INF = 0x3f3f3f3f;
struct Edge{
int to,next,cap,flow;
}edge[MAXM];//注意是MAXM
int tol;
int head[MAXN];
void init(){
tol = 2;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw = 0){
edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0;
edge[tol].next = head[u]; head[u] = tol++;
edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0;
edge[tol].next = head[v]; head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){
int front = 0,tail = 0;
memset(dep,-1,sizeof(dep[0])*(n+1));
dep[s] = 0;
Q[tail++] = s;
while(front < tail){
int u = Q[front++];
for(int i = head[u]; i != -1;i = edge[i].next){
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && dep[v] == -1){
dep[v] = dep[u] + 1;
if(v == t)return true;
Q[tail++] = v;
}
}
}
return false;
}
int dinic(int s,int t,int n){
int maxflow = 0;
while(bfs(s,t,n)){
for(int i = 0;i < n;i++)cur[i] = head[i];
int u = s, tail = 0;
while(cur[s] != -1){
if(u == t){
int tp = INF;
for(int i = tail-1;i >= 0;i–)
tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
maxflow += tp;
for(int i = tail-1;i >= 0;i–){
edge[sta[i]].flow += tp;
edge[sta[i]^1].flow -= tp;
if(edge[sta[i]].cap-edge[sta[i]].flow == 0)
tail = i;
}
u = edge[sta[tail]^1].to;
}
else if(cur[u] != -1 && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] + 1 == dep[edge[cur[u]].to]){
sta[tail++] = cur[u];
u = edge[cur[u]].to;
}
else {
while(u != s && cur[u] == -1)
u = edge[sta[–tail]^1].to;
cur[u] = edge[cur[u]].next;
}
}
}
return maxflow;
}
int a[510];
int b[510];
int id[510][510];

bool vis[MAXN],no[MAXN];
int Stack[MAXN],top;

bool dfs(int u,int pre,bool flag){
vis[u] = 1;
Stack[top++] = u;
for(int i = head[u];i != -1;i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap <= edge[i].flow)continue;
if(v == pre)continue;
if(!vis[v]){
if(dfs(v,u,edge[i^1].flow < edge[i^1].cap))return true;
}
else if(!no[v])return true;
}
if(!flag){
while(1){
int v = Stack[–top];
no[v] = true;
if(v == u)break;
}
}
return false;
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n,m,K;
int T;
int iCase = 0;
scanf(“%d”,&T);
while(T–)
{
scanf(“%d%d”,&n,&m);
K = 9;
init();
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
id[i][j] = tol;
addedge(i,j+n,K);
}
int sum1 = 0;
for(int i = 1;i <= n;i++)
{
scanf(“%d”,&a[i]);
sum1 += a[i];
addedge(0,i,a[i]);
}
int sum2 = 0;
for(int i = 1;i <= m;i++)
{
scanf(“%d”,&b[i]);
sum2 += b[i];
addedge(i+n,n+m+1,b[i]);
}
iCase++;
printf(“Case #%d: “,iCase);
if(sum1 != sum2)
{
printf(“So naive!\n”);
continue;
}
int tmp = dinic(0,n+m+1,n+m+2);
//printf(“maxflow : %d\n”,tmp);
if(tmp != sum1)
{
printf(“So naive!\n”);
continue;
}
memset(vis,false,sizeof(vis));
memset(no,false,sizeof(no));
top = 0;
bool flag = dfs(n+m+1,n+m+1,0);
if(flag)
{
printf(“So young!\n”);
continue;
}
printf(“So simple!\n”);
}
return 0;
}