HDU A new Graph Game(花销流)
A new Graph Game
题目链接：Click Here~
题目分析：
给你一张图，图上可能有多个哈密顿回路。叫你求出形成多个哈密顿回路的总距离最小值，即转换成最小花费。为什么形成回路还会有最小值呢？因为这就是费用流有时候不能用邻接矩阵的原因了。费用流一般都会有平行边的存在，所以一般都是用邻接表。
哈密顿图：每个点只能经过有且仅有一次。
欧拉回路：每条边只能有且仅有经过一次。
算法分析：
既然知道了是费用流，当然一遍费用流算法就可以了。但是这题的边密，点多。所以很容易超时，我就在这上面花了好多时间，写了个输入外挂才险过了。现在就开始写KM吧，不然下次比赛超时就不好了^ _ ^
建模分析：
这一题，跟普通的建模方法一样都是拆点，建立超级点。这题有一个需要注意的是，图是无向图，所以要建立边两次，一开始我就一直卡在这里了。但是，经过这题我终于弄懂了，为什么求圈的时候可以直接拆点用费用流了。
下面举两个例子简单的证明一下：
设汇点s，源点t.
----> 输入个边的关系： 拆点建图：
1 2 (1, 2')
2 3 (2, 3')
3 1 (3, 1')
(s,1) (s,2) (s,3)
(1',t) (2',t) (3',t)
----->不知道你发现上面的规律了没有，可能一时难一发现。其实，这就是跟哈密顿回路的性质有关了。因为每个点必须经过一次，且只能是一次。所以你拆点之后，实质上每个点是一一对应的关系的。每个点只能对一个点，且如果存在哈密顿回路的话。每个点必须有一个对立的点链接。这就是为什么费用流有时候也可以用二分匹配的原因了，因为费用流的本质思想我个人认为其实就是二分匹配。所以，最后我检验是否有回路的时候，只要检查是否每个点都有可匹配的点就可以了。即最大流为n。
先给个搓搓的代码，只有c++提交才能过^_^
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = ~0U>>2;
const int MAXN = 2e3+10;
struct Edge{
int from,to,cap,flow,cost;
Edge(int f,int t,int c,int _f,int _c)
:from(f),to(t),cap(c),flow(_f),cost(_c){}
};
class MCMF{
public:
void Init(int n)
{
s = 0; t = n+n+1;
for(int i = 0;i <= n;++i)
f[i] = i;
for(int i = 0;i <= t;++i)
G[i].clear();
edges.clear();
}
int Read()
{
char ch = getchar();
while(!isdigit(ch))ch = getchar();
int sum = 0;
while(isdigit(ch)){
sum *= 10;
sum += ch-'0';
ch = getchar();
}
return sum;
}
void AddEdge(int from,int to,int cap,int cost)
{
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
int sz = edges.size();
G[from].push_back(sz-2);
G[to].push_back(sz-1);
}
// int Find(int x);
// void Union(int u,int v);
// bool Judege(int u,int v);
void Solve(int n,int m)
{
Init(n);
int x,y,c;
for(int i = 1;i <= n;++i){
AddEdge(s,i,1,0);
AddEdge(i+n,t,1,0);
}
for(int i = 0;i < m;++i){
x = Read();
y = Read();
c = Read();
// Union(x,y);
AddEdge(x,y+n,1,c);
AddEdge(y,x+n,1,c);
}
}
int Mincost(int& flow,int cost)
{
while(BellmanFord(flow,cost));
return cost;
}
bool BellmanFord(int& flow,int& cost)
{
for(int i = 0;i <= t;++i)d[i] = INF;
memset(inq,false,sizeof(inq));
inq[s] = true;d[s] = 0;a[s] = INF;p[s] = 0;
queue<int> Q;
Q.push(s);
while(!Q.empty()){
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i = 0;i < (int)G[u].size();++i){
Edge& e = edges[G[u][i]];
if(e.cap > e.flow&&d[e.to] > d[u]+e.cost){
d[e.to] = d[u]+e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u],e.cap-e.flow);
if(!inq[e.to]){Q.push(e.to);inq[e.to] = true;}
}
}
}
if(d[t]==INF)return false;
int u = t;
flow += a[t];
cost += a[t]*d[t];
while(u != s){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
private:
vector<Edge> edges;
vector<int> G[MAXN];
int n,m,s,t;
int f[MAXN],d[MAXN],p[MAXN],a[MAXN];
bool inq[MAXN];
};
//inline int MCMF::Find(int x)
//{
// if(f[x]==x)
// return f[x];
// return f[x] = Find(f[x]);
//}
//inline void MCMF::Union(int u,int v)
//{
// int a = Find(u),b = Find(v);
// if(a != b)
// f[a] = b;
//}
//bool MCMF::Judege(int u,int v)
//{
// return Find(u)==Find(v);
//}
MCMF mcmf;
int main()
{
int T,n,m;
scanf("%d",&T);
for(int kase = 1;kase <= T;++kase)
{
scanf("%d%d",&n,&m);
mcmf.Solve(n,m);
int cost = 0,flow = 0;
cost = mcmf.Mincost(flow,cost);
if(flow==n){
printf("Case %d: %d\n",kase,cost);
}
else
printf("Case %d: NO\n",kase);
}
return 0;
}
刚学的EK算法，因为KM是O(N^4)的所以懒得写了。对KM算法的理解，我个人学习的时候感觉是在松弛的时候有点不明白，后来通过反复的查找资料。终于弄懂了，好开心 ^_^
为什么在松弛的时候要把左自己的S[]集合的数减去a呢？而又把T[]集合的数加上a呢？
这是因为我们之所以，会把顶标加到S[]和T[]中。是因为L(x)+L(y) = w(x,y)，显然，这时候如果我们把L(x)的值减了一个a,此时的等式显然不等。所以为了让等式相等，我们就要把L(y)加上a。这就是我对这个松弛操做的理解。因为，我学习算法的资料最要是LRJ的书。所以，用的名词都是那书上的，我就不解释那名词的意思了，如果不懂得话，自己在看别的资料吧。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = ~0U>>2;
const int MAXN = 1e3 + 5;
const int MAXM = 1e4 + 5;
int top,Head[MAXN],Next[2*MAXM],Key[2*MAXM],W[2*MAXM];
int n,m,slack,Lx[MAXN],Ly[MAXN],Left[MAXN],Sum[MAXN];
bool T[MAXN],S[MAXN];
void AddEdge(int u,int v,int c)
{
int e;
for(e = Head[u];e != -1;e = Next[e])
if(Key[e]==v)break;
if(e==-1){
Key[top] = v;
W[top] = c;
Next[top] = Head[u];
Head[u] = top++;
return;
}
if(W[e] < c)
W[e] = c;
}
void Init()
{
int x,y,c;
top = 0;
memset(Head,-1,sizeof(Head));
for(int i = 0;i < m;++i){
scanf("%d%d%d",&x,&y,&c);
AddEdge(x,y,-c);
AddEdge(y,x,-c);
}
}
bool Match(int u)
{
int e,tmp;
S[u] = true;
for(e = Head[u];e != -1;e = Next[e]){
int v = Key[e];
if(!T[v]){
tmp = Lx[u]+Ly[v]-W[e];
if(tmp == 0){
T[v] = true;
if(Left[v]==-1||Match(Left[v])){
Left[v] = u;
Sum[v] = W[e];
return true;
}
}
else if(tmp < slack)
slack = tmp;
}
}
return false;
}
void Update(int slack)
{
for(int i = 1;i <= n;++i){
if(S[i]) //一增一减，保持L(x)+L(y) = W(x,y)的值不变
Lx[i] -= slack;
if(T[i])
Ly[i] += slack;
}
}
bool EK()
{
int u,e;
for(u = 1;u <= n;++u){
Lx[u] = Ly[u] = 0;
for(e = Head[u];e != -1;e = Next[e])
Lx[u] = max(Lx[u],W[e]);
}
memset(Left,-1,sizeof(Left));
for(int u = 1;u <= n;++u){
for(;;){
slack = INF;
memset(S,false,sizeof(S));
memset(T,false,sizeof(T));
if(Match(u))
break;
if(slack == INF)
return false;
Update(slack);
}
}
return true;
}
int GetAns()
{
int ans = 0;
for(int i = 1;i <= n;++i)
ans += -Sum[i];
return ans;
}
int main()
{
// freopen("Input.txt","r",stdin);
// freopen("Out.txt","w",stdout);
int T;
scanf("%d",&T);
for(int kase = 1;kase <= T;++kase){
scanf("%d%d",&n,&m);
Init();
if(EK())
printf("Case %d: %d\n",kase,GetAns());
else
printf("Case %d: NO\n",kase);
}
return 0;