bzoj5154 [Tjoi2014]匹配

bzoj5154 [Tjoi2014]匹配

​​ Description

有N个单身的男孩和N个单身女孩，男孩i和女孩j在一起得到的幸福值为Hij。一个匹配即对这N个男孩女孩的安排： 每个男孩恰好有一个女朋友，每个女孩恰好有一个男朋友。一个匹配的幸福值即这N对男女朋友的幸福值的和。经 典的问题是计算幸福值最大的匹配，即完美匹配。然而完美匹配有时候并不唯一，你需要计算，对于所有的完美匹 配，其交集是什么。

Input

输入的第一行是一个正整数N。N ≤ 80 接下来是一个N*N大小的矩阵H，Hij表示男孩i和女孩j在一起的幸福值。(0≤Hij≤5000)

Output

第一行输出完美匹配的幸福值 接下来是若干行，每一行是一对整数i和j，表示男孩i和女孩j在所有完美匹配的交集中。以i的递增顺序输出

Sample Input

3 1 1 1 2 1 1 1 1 1 Sample Output

4 2 1 HINT

Source

一开始觉得暴力能过 仔细分析复杂度觉得有问题 但是还是写了T飞 然后仔细分析发现不需要n^2枚举边 只需要枚举那些有流量的边即可 然后AC

#include#include#include#include#include#define inf 0x3f3f3f3f#define pa pairusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S)return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=200; bool flag[N];int num=1,h[N],pre[N],path[N],dis[N],T;struct node{ int y,next,z,c;}data[15000];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z;data[num].c=c; data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=0;data[num].c=-c;}inline bool spfa(){ memset(pre,-1,sizeof(pre));memset(dis,0x80,sizeof(dis)); queueq;q.push(0);dis[0]=0;memset(flag,0,sizeof(flag));flag[0]=1; while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if (dis[x]+c>dis[y]&&z){ dis[y]=dis[x]+c;pre[y]=x;path[y]=i; if (!flag[y]){ q.push(y);flag[y]=1; } } } }return pre[T]!=-1;}pa q[10000];int top,n,a[88][88],ans,mp[88][88];int main(){ freopen("bzoj5154.in","r",stdin); n=read();T=(n<<1)+1; for (int i=1;i<=n;++i) insert1(0,i,1,0),insert1(i+n,T,1,0); for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) a[i][j]=read(),insert1(i,j+n,1,a[i][j]); while(spfa()){ int minn=inf,now=T; while(now) minn=min(minn,data[path[now]].z),now=pre[now];ans+=dis[T]*minn;now=T; while(now) data[path[now]].z-=minn,data[path[now]^1].z+=minn,now=pre[now]; } for (int i=1;i<=n;++i){ for (int j=h[i];j;j=data[j].next){ int y=data[j].y; if(y>n&&y

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。