all the possible case i consider
but i can not rmove WA ,Plz give me some critical input
plz .......................
thanks in advance.
11506 - Angry Programmer
Moderator: Board moderators
Re: 11506 - Angry Programmer
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.
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.
-
- New poster
- Posts: 4
- Joined: Fri Oct 02, 2009 4:06 pm
Re: 11506 - Angry Programmer
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
.
Thanks
Thanks very much
If you found it complicated or unreadable, don't disturb yourselves with reading it
![:D](./images/smilies/icon_biggrin.gif)
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;
}
-
- New poster
- Posts: 4
- Joined: Fri Oct 02, 2009 4:06 pm
Re: 11506 - Angry Programmer
Finally got it AC ![:D](./images/smilies/icon_biggrin.gif)
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
![:D](./images/smilies/icon_biggrin.gif)
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
Hope this helpsoutput
4
3
4
0
Re: 11506 - Angry Programmer
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!
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;
}
Re: 11506 - Angry Programmer
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)
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
Hey guys I am getting lots of wa can anyone help here is my code :
I passed all the tests here and on udebug but stul getting wa please help
Thank you !
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;
}
![:D](./images/smilies/icon_biggrin.gif)