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

## 为什么最小费用流算法里求最短路时改进过的Dijkstra要比Bellman_Ford要慢呢？？

Posted by Der at 2014-04-26 16:51:37 on Problem 2135
```#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <fstream>

using namespace std;

const int maxn=10010;
const int INF=0x7fffffff;
int N,M;
int a[maxn],b[maxn],c[maxn];
struct edge {
int to,cap,cost,rev;
};
int V;
vector<edge> G[maxn];
int dist[maxn];
int prevv[maxn],preve[maxn];
/*
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}

int min_cost_flow(int s,int t,int f)
{
int res=0;
while (f>0) {
fill(dist, dist+V, INF);
dist[s]=0;
bool update=true;
while (update) {
update=false;
for (int v=0; v<V; v++) {
if (dist[v]==INF) {
continue;
}
for (int i=0; i<G[v].size(); i++) {
edge &e=G[v][i];
if (e.cap>0&&dist[e.to]>dist[v]+e.cost) {
dist[e.to]=dist[v]+e.cost;
prevv[e.to]=v;
preve[e.to]=i;
update=true;
}
}
}
}
if (dist[t]==INF) {
return -1;
}
int d=f;
for (int v=t; v!=s; v=prevv[v]) {
d=min(d,G[prevv[v]][preve[v]].cap);
}
f-=d;
res+=d*dist[t];
for (int v=t; v!=s; v=prevv[v]) {
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rev].cap+=d;
}
}
return res;
}
*/
int h[maxn];
typedef pair<int, int> P;
void add_edge(int from,int to,int cap,int cost)
{
G[from].push_back((edge){to,cap,cost,(int)G[to].size()});
G[to].push_back((edge){from,0,-cost,(int)G[from].size()-1});
}

int min_cost_flow(int s,int t,int f)
{
int res=0;
fill(h, h+V, 0);
while (f>0) {
priority_queue<P,vector<P>,greater<P> > que;
fill(dist, dist+V, INF);
dist[s]=0;
que.push(P(0,s));
while (!que.empty()) {
P p=que.top();
que.pop();
int v=p.second;
if (dist[v]<p.first) {
continue;
}
for (int i=0; i<G[v].size(); i++) {
edge &e=G[v][i];
if (e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]) {
dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dist[e.to],e.to));
}
}
}
if (dist[t]==INF) {
return -1;
}
for (int v=0; v<V; v++) {
h[v]+=dist[v];
}
int d=f;
for (int v=t; v!=s; v=prevv[v]) {
d=min(d,G[prevv[v]][preve[v]].cap);
}
f-=d;
res+=d*h[t];
for (int v=t; v!=s; v=prevv[v]) {
edge &e=G[prevv[v]][preve[v]];
e.cap-=d;
G[v][e.rev].cap+=d;
}
}
return res;
}

int main()
{
//freopen("/Users/apple/Desktop/2135/2135/in", "r", stdin);
//freopen("/Users/apple/Desktop/2135/2135/out", "w", stdout);
while ((scanf("%d%d",&N,&M))!=EOF) {
V=N;
for (int i=0; i<M; i++) {
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
int s=0,t=N-1;
for (int i=0; i<M; i++) {
}
int res2=min_cost_flow(s, t, 2);
printf("%d\n",res2);
}
return 0;
}
```

Followed by: