11506 - Angry Programmer

[MRH]

all the possible case i consider
but i can not rmove WA ,Plz give me some critical input
plz .......................
thanks in advance.

[roticv]

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.

[multisystem]

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 adjMax[MAX][MAX], prev[MAX], size;
 
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];
			tmp = adjMax[nxt][i];
 
			if (dist[i] < min(dist[nxt], adjMax[nxt][i]) && adjMax[nxt][i]
					!= 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;
	adjMax[prev[d]][d] -= r, adjMax[d][prev[d]] += r;
	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);
	}
	return totalFlow;
}
 
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;
			adjMax[n][n + m] = c;
			adjMax[n + m][n] = c;
		}
		adjMax[1][1 + m] = OO2;
		adjMax[1 + m][1] = OO2;
		adjMax[m][m + m] = OO2;
		adjMax[m + m][m] = OO2;
		for (int t = 1; t <= w; t++) {
			int f, t, cost;
			cin >> f >> t >> cost;
          if(adjMax[f + m][t] != OO ||	adjMax[t][f + m] !=OO){
			adjMax[f + m][t] += cost;
			adjMax[t][f + m] += cost;}
			else {
                 adjMax[f + m][t] = cost;
			adjMax[t][f + m] = cost;}
 
		}
 
		cout << maxFlow(1, m + m) << endl;
	}
 
	return 0;
}

Thanks

[multisystem]

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

[lionking]

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));
		/*read input*/
		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;
}

[vsha041]

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)

[khalilw1]

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];
vector<int> adj[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++) {
            int v = adj[u][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++)
            adj[i].clear();
        
        res[0][n] = res[n - 1][n - 1 + n] = int(1e8);
        adj[0].push_back(n);
        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;
            
            adj[id].push_back(id + n);
            adj[id + n].push_back(id);
        }

        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;
            adj[u + n].push_back(v);

            res[v + n][u] += cost;
            adj[v + n].push_back(u);
        }

        ll ans = maxflow(0, n + n - 1);
        printf("%lld\n", ans);
    }
    return 0;
}

I passed all the tests here and on udebug but stul getting wa please help Thank you !