HDU 2426 Interesting Housing Problem 最小费用最大流 or KM算法

本文主要是介绍HDU 2426 Interesting Housing Problem 最小费用最大流 or KM算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题貌似是08年杭州网络赛的题目， 看完题后就发现是个最优匹配问题，用KM或者最小费用最大流做， 就找了个最小费用最大流的模板，改了一下，就能过了、

建图还是比较好想的，建立一个超级源点，一个超级汇点，然后源点与学生连边，流量限制为1，费用为0，汇点与房间连边，流量限制为1， 费用为0， 然后学生与房间之间的边，流量限制是1，费用就是题目给的喜好值了， 注意，每次加边，都要加一个相应的反向边， 就是流量为0， 费用为正向边的负数。

然后题目中要求不能把学生分到不喜欢的房间里，所以碰见喜好值是负数就不管了。 另外，由于是最小费用么，所以所有喜好值都是乘以-1后加进去的，这样求出的最小值，输出的时候再乘以-1就变成最大的了。

最后判断能不能所有学生都分配到房间里， 就判断流量的大小是否等于学生个数就行了

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100005
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int tot = 0, x, y;
class mincost
{
private:const static int V = 2001; //注意点的个数， 应该为学生+房间+2， 所以至少要开到1002const static int E = 2000001;const static int INF = -1u >> 1;struct Edge{int v, cap, cost;Edge *next;} pool[E], *g[V], *pp, *pree[V];int T, S, dis[V], pre[V];int n, m, flow, cirq[V];void SPFA();inline void addedge(int i, int j, int cap, int cost);
public:bool initialize(int x, int y, int z);void mincost_maxflow();
};void mincost::mincost_maxflow()
{while (true){SPFA();if (dis[T] == INF)break;int minn = INF;for (int i = T; i != S; i = pre[i])minn = min(minn, pree[i]->cap);for (int i = T; i != S; i = pre[i]){pree[i]->cap -= minn;pool[(pree[i] - pool)^0x1].cap += minn;flow += minn * pree[i]->cost;}tot += minn;  //流量计算}if(tot != x) flow = 1;printf("%d\n", -flow);
}void mincost::SPFA()
{bool vst[V] = {false};int tail = 0, u;fill(dis,dis + n,0x7fffffff);cirq[0] = S;vst[S] = 1;dis[S] = 0;for (int i = 0; i <= tail; i++){int v = cirq[i % n];for (Edge *i = g[v]; i != NULL; i = i->next){if (!i->cap)continue;u = i->v;if (i->cost + dis[v] < dis[u]){dis[u] = i->cost + dis[v];pree[u] = i;pre[u] = v;if (!vst[u]){tail++;cirq[tail % n] = u;vst[u] = true;}}}vst[v] = false;}
}void mincost::addedge(int i, int j, int cap, int cost)
{pp->cap = cap;pp->v = j;pp->cost = cost;pp->next = g[i];g[i] = pp++;
}
bool mincost::initialize(int x, int y, int z)
{memset(g, 0, sizeof (g));pp = pool;n = x + y + 2;  //n即为顶点的个数   学生数+房间数+一个源点+一个汇点m = z;S = 0;T = x + y + 1;int v, u, f, c;for (int i = 0; i < m; i++){scanf("%d %d %d", &v, &u, &c);v++;u++;if(c >= 0){addedge(v, u + x, 1, -c);addedge(u + x, v, 0, c);}}for(int i = 1; i <= x; i++){addedge(0, i, 1, 0);addedge(i, 0, 0, 0);}for(int i = 1; i <= y; i++){addedge(x + i, T, 1, 0);addedge(T, x + i, 0, 0);}flow = 0;return true;
}
mincost g;
int main()
{//freopen("d:/data.in","r",stdin);//freopen("d:/data.out","w",stdout);int  z, cas = 0;while(scanf("%d%d%d", &x, &y, &z) != EOF){g.initialize(x, y, z);printf("Case %d: ", ++cas);tot = 0;g.mincost_maxflow();}return 0;
}

接下来是KM算法的 最后判断是否完备匹配就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 505
#define MAXM 555555
#define INF 1000000000
using namespace std;
int n, m, ny, nx;
int w[MAXN][MAXN];
int lx[MAXN], ly[MAXN];
int linky[MAXN];
int visx[MAXN], visy[MAXN];
int slack[MAXN];
bool find(int x)
{visx[x] = 1;for(int y = 1; y <= ny; y++){if(visy[y]) continue;int t = lx[x] + ly[y] - w[x][y];if(t == 0){visy[y] = 1;if(linky[y] == -1 || find(linky[y])){linky[y] = x;return true;}}else if(slack[y] > t) slack[y] = t;}return false;
}
void KM()
{memset(linky, -1, sizeof(linky));for(int i = 1; i <= nx; i++) lx[i] = -INF;memset(ly, 0, sizeof(ly));for(int i = 1; i <= nx; i++)for(int j = 1; j <= ny; j++)if(w[i][j] > lx[i]) lx[i] = w[i][j];for(int x = 1; x <= nx; x++){for(int i = 1; i <= ny; i++) slack[i] = INF;while(true){memset(visx, 0, sizeof(visx));memset(visy, 0, sizeof(visy));if(find(x)) break;int d = INF;for(int i = 1; i <= ny; i++)if(!visy[i]) d = min(d, slack[i]);for(int i = 1; i <= nx; i++)if(visx[i]) lx[i] -=d;for(int i = 1; i <= ny; i++)if(visy[i]) ly[i] += d;else slack[i] -= d;}}
}
int main()
{int x, y, z, e, cas = 0;while(scanf("%d%d%d", &n, &m, &e) != EOF){nx = n, ny = m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)w[i][j] = -INF;while(e--){scanf("%d%d%d", &x, &y, &z);if(z >= 0) w[x + 1][y + 1] = z;}printf("Case %d: ", ++cas);KM();int cnt = 0, ans = 0;for(int i = 1; i <= ny; i++)if(linky[i] != -1 && w[linky[i]][i] != -INF)ans += w[linky[i]][i], cnt++;if(cnt != nx) ans = -1;printf("%d\n", ans);}return 0;
}

这篇关于HDU 2426 Interesting Housing Problem 最小费用最大流 or KM算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---