Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

太诡异了这个题……两份代码对于一个测试数据，结果不一样，可是都AC了……这是什么世道？为什么我的WA？继续调试

Posted by lenglengmajia at 2009-03-24 14:59:30 on Problem 2195
In Reply To:太诡异了这个题……两份代码对于一个测试数据，结果不一样，可是都AC了……这是什么世道？为什么我的WA？继续调试 Posted by:lenglengmajia at 2009-03-24 14:58:51
```#include<iostream>

#define min(a,b) ((a)<(b))?(a):(b)
using namespace std;

bool visited[205];
int house[205][2];
int man[205][2];
char str[205];
int maxflow;

struct Node
{
int pre,flow,cost;

}label[205];

struct edge
{
int cap,currentflow;
int unitcost;

}network[205][205];

void intial(int n)
{
for(int i = 0 ;i < n;i++)
label[i].cost = 1000000000,label[i].flow = 0,label[i].pre = 0;
}

void Intial(int n)
{
for(int i = 0; i < n;i++)
for(int j = 0; j < n;j++)
network[i][j].cap = network[i][j].unitcost = network[i][j].currentflow = 0;
}

struct Vertix
{
int vertix,cost;
Vertix(int v = 0,int c = 0):vertix(v),cost(c){}
bool operator > (const Vertix& lhs) const
{
return (lhs.cost<cost);
}
};

bool modefiedDijkstra(int n,int s,int t)
{
intial(n);
fill_n(visited,n,false);
Vertix w;
w.cost = 0,w.vertix = s;
label[s].pre = -1,label[s].flow = 1000000000,label[s].cost = 0;
int v = 0,u = 0;
while(true)
{
int minv = 1100000000;
for(int w = 0; w < n;w++)
if(!visited[w]&&label[w].cost < minv)
{
v = w,minv = label[w].cost;
}
if(v == t)
if(label[t].cost >= 1000000000)
return false;
else
return true;
visited[v] = true;
for(u = 0; u < n;u++)
if(!visited[u])
{
if(network[v][u].cap > 0&&network[v][u].cap - network[v][u].currentflow > 0&&
label[v].cost + network[v][u].unitcost < label[u].cost)
{
label[u].pre = v;
label[u].cost = label[v].cost + network[v][u].unitcost;
label[u].flow = min(label[v].flow,network[v][u].cap - network[v][u].currentflow);
}
else if(network[u][v].cap > 0&&network[u][v].currentflow > 0&&label[v].cost - network[u][v].unitcost < label[u].cost)
{
label[u].pre = v;
label[u].flow = min(label[v].flow,network[u][v].currentflow);
label[u].cost = label[v].cost - network[u][v].unitcost;
}
}
}
}

void arguementpath(int t)
{
for(int k = t;k != -1;k = label[k].pre)
{
if(network[label[k].pre][k].cap > 0)
network[label[k].pre][k].currentflow += label[t].flow;
else
network[k][label[k].pre].currentflow -= label[t].flow;
printf("%d %d %d ; ",label[k].pre,k,label[k].cost-label[label[k].pre].cost);

}
printf("%d ",label[101].cost-label[66].cost);
printf("%d ",label[66].cost-label[9].cost);
printf("%d ",label[9].cost-label[63].cost);
printf("%d ",label[63].cost-label[26].cost);
printf("%d ",label[26].cost-label[0].cost);
//printf("%d ",label[91].cost-label[42].cost);
//printf("%d ",label[42].cost-label[93].cost);
//printf("%d ",label[93].cost-label[43].cost);
//printf("%d ",network[0][43].currentflow);

//printf("%d ",label[101].cost-label[100].cost);
//printf("%d ",label[101].cost-label[100].cost);
//printf("%d ",label[101].cost-label[100].cost);
printf("\n");
}

void MaxFlowMincostAlgorithm(int n,int s,int t)
{
int mincost = 0;
maxflow=0;
while(modefiedDijkstra(n,s,t))
{
printf("%d ",label[t].cost);
arguementpath(t);
maxflow+=label[t].flow;
mincost += label[t].cost;

}
printf("%d\n",mincost);
printf("%d\n",maxflow);
}

void add(int x,int y,int cap,int cost)
{
network[x][y].cap += cap;
network[x][y].unitcost += cost;
}

int ABS(int num)
{
return num > 0 ? num:(-num);
}

int main()
{

int N,M,m,h,i,j;
while ( scanf ( "%d%d", &N, &M ) && ( N || M ) )
{
m = 0,h = 0;
for (i = 0; i < N; i++ )
{
scanf ( "%s", &str );
for (j = 0; j < M; j++)
{
if (str[j] == 'H')
{
house[h][0] = i;
house[h][1] = j;
h++;
continue;
}
if (str[j] == 'm')
{
man[m][0] = i;
man[m][1] = j;
m++;
continue;
}
}
}
Intial(m + h + 2);
for (i = 0; i < m; i++)
add (0,i + 1,1,0);
for (i = 0; i < m; i++)
{
for (j = 0; j < h; j++ )
{
int weight = ABS(man[i][0]-house[j][0]) + abs(man[i][1]-house[j][1]);
add (i + 1,m + j + 1,1,weight);
}
}

for ( j = 0; j < h; j++ )
add (m + j + 1, m + h + 1,1,0);
MaxFlowMincostAlgorithm(m + h + 2,0,m + h + 1);
}
return 0;
}

Followed by: