奔小康赚大钱Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10760 Accepted Submission(s): 4765Problem Description传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须...
1076. Trash Time limit: 1.0 second Memory limit: 64 MBYou were just hired as CEO of the local junkyard.One of your jobs is dealing with the incoming trash and sorting it for recycling.The trash comes every day in N containers and each of thesecontainers contains certain amount of each of the N types of trash. Given the amount of trash in the containers find the optimal way to sort the trash. Sorti...
PS：其实不用理解透增广路，交替路，网上有对代码的形象解释，看懂也能做题，下面我尽量把原理说清楚基本概念 （部分来源、部分来源）二分图： 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。匹配： 一个匹配即一个包含若干条边的集合，且其中任意两条边没有公共端点。下图标红的边即为匹配? ...
题目大意：求二分图的最优匹配（首先数目最大， 其次权值最大）。解题关键：KM算法复杂度：$O(n^3)$#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<iostream> #include<cmath> usingnamespace std; typedef longlong ll; constint N=310; constint inf=0x3f3f3f3f; int nx,ny; int g[N][N]; int match[N],lx[N],ly[N];//y中各点匹配状态，x,y中的顶点标号int slack[N]; bool visx[N],visy[N]...
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价...
http://acm.hdu.edu.cn/showproblem.php?pid=4862选t<=k次，t条路要经过所有的点一次并且仅仅一次，建图是问题： 我自己最初就把n*m 个点分别放入X集合以及Y集合，再求最优匹配，然后连样例都过不了，而且其实当时解释不了什么情况下不能得到结果，因为k此这个条件相当于没用上。。。建图方法： 1、X集合和Y集合都放入n*m+k个点，X中前n*m个点和Y中前n*m个点之间，如果格子里的值相等，权就是（收益-耗费），不等就是（-耗费），因...
KM算法 1 #include <bits/stdc++.h>2#define N 15003#define inf 9999999994usingnamespace std;5int a[N],bs[N],nx=0,ny=0,k;6int linky[N],lx[N],ly[N],slack[N];7int visx[N],visy[N],w[N][N];8int min(int a,int b){return (a<b)?a:b;}9int find(int x){ 10 visx[x]=1; 11for(int y=1;y<=ny;y++){ 12if(visy[y]) continue; 13int t=lx[x]+ly[y]-w[x][y]; 14if(t==0){visy[y]=1; 15if(linky[y]==-1||find(linky[y])){ 16 ...
二分图最大权值匹配问题。用KM算法。最小权值的时候把权值设置成相反数 1/*--------------------------------------------------------------------------------------*/ 2 3 #include <algorithm>4 #include <iostream>5 #include <cstring>6 #include <ctype.h>7 #include <cstdlib>8 #include <cstdio>9 #include <vector>10 #include <string>11 #include <queue>12 #include <stack>13 #include <cmath>14 #include <set>1...
1//hdu1853 2 #include<stdio.h>3 #include<string.h>4#define INF 999999995int map[103][103],pr[103],pl[103],visr[103],visl[103],slack[103],match[103];6int n,m;7int dfs(int u)8{9int i,j,val;10 11 visl[u]=1;12for(i=1;i<=n;i++)13 {14if(!visr[i])15 {16 val=pr[i]+pl[u]-map[u][i];17if(val==0)18 {19 visr[i]=1;20if(match[i]==-1||dfs(match[i]))21 ...
【POJ 2195】 Going Home（KM算法求最小权匹配）Going HomeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 20303 Accepted: 10297DescriptionOn a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for everystep he moves, until he ...
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价...
KM算法计算带权二分图最优匹配 时间复杂度\(O(n^3)\) 模板题：hdu2255 奔小康赚大钱 const int maxn=310; const int inf=0x3f3f3f3f;int n; int g[maxn][maxn],ex1[maxn],ex2[maxn],match[maxn],slack[maxn]; bool vis1[maxn],vis2[maxn];bool dfs(int x){vis1[x]=true;for(int y=0;y<n;y++) {if(vis2[y]) continue; int gap=ex1[x]+ex2[y]-g[x][y];if(gap==0){ vis2[y]=true;if(match[y]==-1 || dfs(match[y])){ match[y]=...
题目链接：[传送门](https://www.luogu.com.cn/problem/UVA11383) ## 分析 这道题乍看上去没有思路，但是我们仔细一想就会发现这道题其实是一个二分图最大匹配的板子 我们可以把这道题想象成将男生和女生之间两两配对，使他们的好感度最大 我们把矩阵中的元素$a[x][y]$看成女生$x$和男生$y$之间的好感度，跑一个KM算法 因为KM算法会维护$ex_{}boy[x] + ex_{}girl[y]>=love[y][x]$，所以最后的结果就是我们想要的 注意有多组数据 ##...
二分图[匈牙利算法 & KM算法] 概念二分图：把一个图的顶点划分为两个不相交集 U 和V ，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图 3、图 4 中红色的边就是图 2的匹配。我们定义匹配点、匹配边、未匹配点、非匹配边，例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；(1,5)、(4,7)为匹配...
二分图最大带权匹配。 输入点的个数和各边权值，输出最大匹配的权值和。 1 #include<iostream>2 #include<cstdio>3 #include<cstring>4 5 using namespace std;6 7 const int N=310;8 const int INF=0x3f3f3f3f;9 10 int n,nx,ny; 11 int linker[N],lx[N],ly[N],slack[N]; //lx,ly为顶标，nx,ny分别为x点集y点集的个数 12 int visx[N],visy[N],w[N][N]; 13 14 int DFS(int x){ 15 visx[x]=1; 16 for(int y=1;y<=ny;...