HDU2255 奔小康赚大钱 又是984ms 飘过汗啊 最大权匹配 KM算法模版题
最近跟984ms很有爱啊，再次以984ms飘过！！！
这道题不可以说是模版题目，因为它就是个模版，简直就是一模一样的模版，做了这道题你就知道什么是模版，模版长什么样子了，
我反正照着模版打的，打出来跟模版长得一样
题目是中文的 不用解释了
先贴一个模版
想要快点的 自己改成个邻接表形式的就可以了
#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-8const 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方点的标号全部加上一个常数dfor(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;elseslack[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;}}