4最⼩费⽤最大流1
需积分: 0 124 浏览量
2022-08-08
22:25:38
上传
评论
收藏 13KB DOCX 举报
UVa1658
题意：给定 v（3<=v<=1000)个节点，e(3<=e<=10000)条边的又向加权图，求 1->v 的两条
不相交的路径，使得权和最小。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define clc(a,b) memset(a,b,sizeof(a))
#define MAXN 2010
#define INF 0x3f3f3f3f
typedef long long LL;
struct MCMF{
int n,m;
struct Edge{
int from, to, cap, flow, cost;
Edge(int a, int b, int c, int d, int e){
from = a, to = b, cap = c, flow = d, cost = e;
}
};
vector<Edge> edge;
vector<int> g[MAXN];
bool inq[MAXN];
int d[MAXN]/*spfa*/, p[MAXN]/*上一条弧*/, a[MAXN]/*可改进量*/;
void init(int n){
this->n = n;
repe(i,1,n) g[i].clear();
edge.clear();
}
void add_edge(int from, int to, int cap, int cost)
{
edge.push_back(Edge(from,to,cap,0,cost));
edge.push_back(Edge(to,from,0,0,-cost));
m = edge.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
}
bool spfa(int s, int t, int& flow, LL& cost)
{
clc(d,0x3f);
clc(inq,0);
评论0