Page 1 of 1

### 11506 - Angry Programmer

Posted: Wed Apr 08, 2009 11:00 am
all the possible case i consider
but i can not rmove WA ,Plz give me some critical input
plz .......................

### Re: 11506 - Angry Programmer

Posted: Sun Apr 26, 2009 4:17 am
Did you decompose the undirected edges to directed edges?
Did you link the in-nodes to out-nodes and out-nodes to in-nodes correctly?

I think your problem should be one of the two cases.

### Re: 11506 - Angry Programmer

Posted: Fri Oct 02, 2009 4:09 pm
This code gives WA, don't know why.

Thanks very much

If you found it complicated or unreadable, don't disturb yourselves with reading it .

Code: Select all

``````
#include<cmath>
#include<vector>
#include<iostream>
#include<algorithm>
#include <map>
using namespace std;
const int OO = 100000000;
const int OO2 = 1000000;
const int MAX = 300;

int Dijkstra_maxmini(int src, int end) {

memset(prev, -1, sizeof(prev));
vector<int> dist(size, 0);
vector<int> vis(size, 0);

dist[src] = OO;
for (int k = 1; k < size; k++) {

int maxi = 0, nxt = -1;
for (int i = 1; i < size; i++)
if (!vis[i] && dist[i] > maxi)
nxt = i, maxi = dist[i];

if (nxt == end)
return dist[end];
if (nxt == -1)
return -1;

vis[nxt] = 1;
for (int i = 1; i < size; i++) {
int tmp = dist[i];
tmp = dist[nxt];

!= OO)
dist[i] = max(dist[i], min(dist[nxt], adjMax[nxt][i])), prev[i]
= nxt;

}
}
return -1;
}

void removePath(int src, int d, int r) {
if (d == src)
return;
removePath(src, prev[d], r);
}

int maxFlow(int src, int des) {
int totalFlow = 0, ret = 0;
while ((ret = Dijkstra_maxmini(src, des)) && ret != -1) {
totalFlow += ret;
removePath(src, des, ret);
}
}

int main() {

int m, w, n, c;

while (cin >> m >> w) {

if (m == 0 && w == 0)
break;
size = m + m + 1;

for (int i = 1; i <= size; ++i) {
for (int j = 1; j <= size; ++j) {
adjMax[i][j] = OO; // no path
}
}

for (int i = 1; i <= m - 2; i++) {
cin >> n >> c;
}
for (int t = 1; t <= w; t++) {
int f, t, cost;
cin >> f >> t >> cost;
else {

}

cout << maxFlow(1, m + m) << endl;
}

return 0;
}

``````
Thanks

### Re: 11506 - Angry Programmer

Posted: Fri Oct 02, 2009 10:15 pm
Finally got it AC

Here is some hints

Read carefully the problem text, specially

1-There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.

2- i<k --> 1 <= j < k <= M

3- the wire is bidirectional.

This hint also is very useful,
http://www.comp.nus.edu.sg/~stevenha/pr ... Programmer

From this hint, you can say
If you have 4 nodes, then split them to 8 nodes. The first four nodes are the innodes and the last ones are the outnodes.
To connect node 1 to node 2, then
connect node 5 to node 2 with the cost, and connect node 6 with node 1 with the cost.

In my code, I initialized adjMax[][] with infinity. The right is to initialize it with 0.

Finally, Some useful test cases
input
4 4
3 5
2 2
1 2 3
1 3 3
2 4 1
3 4 3

4 4
3 2
2 2
1 2 3
1 3 3
2 4 1
3 4 3

4 6
3 0
2 0
1 2 100000
1 3 100000
1 4 4
2 4 100000
2 3 100000
3 4 100000

4 2
2 4
3 4
1 2 5
1 3 6
output

4
3
4
0
Hope this helps

### Re: 11506 - Angry Programmer

Posted: Thu Nov 05, 2009 6:28 am
I got WA of this code.

But I don't understand where I wrong?

I have try many test cases, and it all correct

could someone help me?

thx!

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <queue>
#define MACHINE 100

using namespace std;

typedef int graph[MACHINE][MACHINE];
graph C, F, R;
bool visit[MACHINE];
int path[MACHINE];
int flow[MACHINE];

int BFS(int s, int t)
{
memset(visit, false, sizeof(visit));
queue<int> Q;
visit[s] = true;
path[s] = s;
flow[s] = 1e9;
Q.push(s);

int i, j;
while(!Q.empty()){
i = Q.front(); Q.pop();
for(j=0; j<10; ++j){
if (!visit[j] && R[i][j] > 0){
visit[j] = true;
path[j] = i;
flow[j] = min(flow[i], R[i][j]);
Q.push(j);

if (j == t) return flow[t];
}
}
}
return 0;
}

int Edmonds_Karp(int s, int t)
{
memset(F, 0, sizeof(F));
memcpy(R, C, sizeof(C));
int f = 0, df, i, j;
for (f=0; (df=BFS(s, t)); f+=df){
for (i=path[t], j=t; i!=j; i=path[j=i]){
F[i][j] = F[i][j] + df;
F[j][i] = -F[i][j];
R[i][j] = C[i][j] - F[i][j];
R[j][i] = C[j][i] - F[j][i];
}
}
return f;
}

int main()
{
int M, W, pi, pj, i, temp, cost;
while(scanf("%d%d", &M, &W)>0 && M>0 &&W>0){
memset(C, 0, sizeof(C));
for(i=1; i<M-1; ++i){
scanf("%d%d", &pi, &cost);
temp = (pi-1)<<1;
C[temp][temp+1] = cost;
C[temp+1][temp] = cost;
}
for(i=0; i<W; ++i){
scanf("%d%d%d", &pi, &pj, &cost);
C[(pi-1)<<1][(pj<<1)-1] = cost;
C[(pj-1)<<1][(pi<<1)-1] = cost;
}
printf("%d\n", Edmonds_Karp(0, (M<<1)-1));
}
return 0;
}``````

### Re: 11506 - Angry Programmer

Posted: Wed Apr 02, 2014 12:23 pm
The main thing in this problem is to build the graph correctly. If you split a node, make sure you add two edges between Vin and Vout. The edge Vin - Vout will have the cost specified in the question. The back edge Vout - Vin will have cost 0 initially.

Now for edges between nodes, you will need 2 forward and 2 residual edges (directed)

V1out -> V2in (cost mentioned in the question)
V2out -> V1in (cost mentioned in the question)
V2in -> V1out (residual/backedge, cost 0 initially)
V1in -> V2out (residual/backedge, cost 0 initially)

### Re: 11506 - Angry Programmer

Posted: Sun Sep 06, 2015 6:48 pm
Hey guys I am getting lots of wa can anyone help here is my code :

Code: Select all

``````
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

#define N 202

typedef long long ll;

ll res[N][N], p[N];

bool bfs(int s, int t) {
int vis[N];
queue<int> Q;

memset(p, -1, sizeof p);
memset(vis, 0, sizeof vis);

Q.push(s);
vis[s] = 1;

while( !Q.empty() ) {
int u = Q.front();
Q.pop();

if( u == t ) return true;

for(int i = 0; i < adj[u].size(); i++) {
if( res[u][v] && !vis[v] ) {
Q.push(v);
vis[v] = 1;
p[v] = u;
}
}
}

return false;
}

ll augment(int t) {
int cur = t;
ll minEdge = INT_MAX;

while( p[cur] != -1 ) {
minEdge = min(minEdge, res[p[cur]][cur]);
cur = p[cur];
}

cur = t;
while( p[cur] != -1 ) {
res[p[cur]][cur] -= minEdge;
res[cur][p[cur]] += minEdge;

cur = p[cur];
}

return minEdge;
}

ll maxflow(int s, int t) {
ll mf = 0;

while( bfs(s, t) ) {
ll f = augment(t);
mf += f;
}

return mf;
}

int main( void ) {
int n, w, cc = 1;
while(scanf("%d %d", &n, &w) != EOF && (n || w)) {
memset(res, 0, sizeof res);
for(int i = 0; i < N; i++)

res[0][n] = res[n - 1][n - 1 + n] = int(1e8);
adj[n - 1].push_back(n - 1 + n);

for(int i = 0; i < n - 2; i++) {
int id;
ll cost;
scanf("%d %lld", &id, &cost);

id--;

res[id][n + id] += cost;

}

for(int i = 0; i < w; i++) {
int u, v;
ll cost;
scanf("%d %d %lld", &u, &v, &cost);
u--, v--;

res[u + n][v] += cost;