HDU2255 奔小康赚大钱 又是984ms 飘过汗啊 最大权婚配 KM算法模版题
HDU2255 奔小康赚大钱 又是984ms 飘过汗啊 最大权匹配 KM算法模版题
最近跟984ms很有爱啊，再次以984ms飘过！！！
这道题不可以说是模版题目，因为它就是个模版，简直就是一模一样的模版，做了这道题你就知道什么是模版，模版长什么样子了，
我反正照着模版打的，打出来跟模版长得一样
题目是中文的 不用解释了
先贴一个模版
想要快点的 自己改成个邻接表形式的就可以了
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 305;
const int INF = (1<<30)-1;
int g[maxn][maxn];
int lx[maxn],ly[maxn];
int match[maxn];
bool visx[maxn],visy[maxn];
int slack[maxn];
int n;
bool dfs(int cur){
visx[cur] = true;
for(int y=1;y<=n;y++){
if(visy[y]) continue;
int t=lx[cur]+ly[y]-g[cur][y];
if(t==0){
visy[y] = true;
if(match[y]==-1||dfs(match[y])){
match[y] = cur;
return true;
}
}
else if(slack[y]>t){
slack[y]=t;
}
}
return false;
}
int KM(){
memset(match,-1,sizeof(match));
memset(ly,0,sizeof(ly));
for(int i=1 ;i<=n;i++){
lx[i]=-INF;
for(int j=1;j<=n;j++)
if(g[i][j]>lx[i]) lx[i]=g[i][j];
}
for(int x=1;x<=n;x++){
for(int i=1;i<=n;i++) slack[i]=INF;
while(true){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(x)) break;
int d=INF;
for(int i=1;i<=n;i++){
if(!visy[i]&&d>slack[i]) d=slack[i];
}
for(int i=1;i<=n;i++){
if(visx[i]) lx[i]-=d;
}
for(int i=1;i<=n;i++){
if(visy[i]) ly[i]+=d;
else slack[i]-=d;
}
}
}
int result = 0;
for(int i = 1; i <=n; i++)
if(match[i]>-1)
result += g[match[i]][i];
return result;
}
int main(){
while(scanf("%d",&n)!=EOF){
int cost;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
scanf("%d",&cost);
g[i][j]=cost;
}
printf("%d\n",KM());
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define LL __int64
#define eps 1e-8
const ll INF=9999999999999;
using namespace std;
#define M 400000100
#define inf 0xfffffff
//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;
//vector<int>G[8000];
int mp[1212][1212];
int marry[1212];
int lx[1212],ly[1212];
bool visx[1212],visy[1212];
int slack[1212];
int dis[2][4]={0,-1,0,1,1,0,-1,0};
int n,m,k;
int un,vn;
void clear()
{
memset(marry,-1,sizeof(marry));
/*memset(vis,false,sizeof(vis));*/
memset(mp,0,sizeof(mp));
memset(ly,0,sizeof(ly));
/*for(int i=0;i<=m;i++)
G[i].clear();*/
}
bool dfs(int x)
{
visx[x]=true;
for(int i=1;i<=vn;i++)
{
if(visy[i])
continue;
int temp=lx[x]+ly[i]-mp[x][i];
if(temp==0)
{
visy[i]=true;
if(marry[i]==-1 || dfs(marry[i]))
{
marry[i]=x;
return 1;
}
}
else if(slack[i]>temp) //不在相等子图中slack 取最小的
slack[i]=temp;
}
return 0;
}
int KM()
{
int j;
for(int i=1;i<=un;i++)
for(j=1,lx[i]=-inf;j<=vn;j++)//这里注意喔别看花眼
if(mp[i][j]>lx[i])
lx[i]=mp[i][j];
for(int i=1;i<=un;i++)
{
for(j=0;j<=vn;j++)
slack[j]=inf;
while(1)
{
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(i))//若成功（找到了增广轨），则该点增广完成，进入下一个点的增广
break;//若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增
int d=inf; //方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，所有在增广轨中的Y方点的标号全部加上一个常数d
for(j=1;j<=vn;j++)
if(!visy[j] && d>slack[j])
d=slack[j];
for(j=1;j<=un;j++)
if(visx[j])
lx[j]-=d;
for(j=1;j<=vn;j++)//修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d
{
if(visy[j])
ly[j]+=d;
else
slack[j]-=d;
}
}
}
int ans=0;
for(int i=1;i<=vn;i++)
if(marry[i]>-1)
ans+=mp[marry[i]][i];
return ans;
}
int main(void)
{
while(cin>>n)
{
un=vn=n;//最好改一下，不要只用n，这样能让自己时刻保持在对哪个集合中的点进行操作
clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];//其实我的984ms造成的原因在这里，用cin更会耗时，改成scanf就变成400+ms，毕竟n有300那么大
int ans=KM();
cout<<ans<<endl;
}
}