首页 > 代码库 > hdu 3081 hdu 3277 hdu 3416 Marriage Match II III IV //最大流的灵活运用
hdu 3081 hdu 3277 hdu 3416 Marriage Match II III IV //最大流的灵活运用
3081 题意:
n个女孩选择没有与自己吵过架的男孩有连边(自己的朋友也算,并查集处理),2分图,有些边,求有几种完美匹配(每次匹配每个点都不重复匹配)
我是建二分图后,每次增广一单位,(一次完美匹配),再修改起点还有终点的边流量,继续增广,直到达不到完美匹配为止。网上很多是用二分做的,我觉得没必要。。。(网上传播跟风真严重。。。很多人都不是真正懂最大流算法的。。。)
3277 :
再附加一条件,每个女孩可以最多与k个自己不喜欢的男孩。求有几种完美匹配(同上)。
我觉得:求出上题答案,直接ans+k即可(大于n取n),因为,最多是n种匹配。在限制的基础上,求出最大值,然后余下的k种,是随意连边的,总有完美匹配方案吧?当然不大于n,我是这样想的。不知道为什么WA。。。。感觉没问题。。。网上大多是拆点,连自己不喜欢的边,跑最大流(盲目跟风解法,不经思考的人很厌恶。。。吐槽几句:当我提出新解法的时候,有“牛”半秒内直接说显然错误。。然后又半天不解释。说:“二分+并查集+拆点+最大流,自己理解”....╮(╯▽╰)╭...呵呵)
3416: 求边不可重复最短路条数。比较简单。跑最短路后,类似dp找出是最短路的边,添加流量为1,直接最大流。
代码3081:
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<set> #include<vector> using namespace std; const int inf=0x3f3f3f3f; const int maxv=210,maxe=40000; int nume=0;int head[maxv];int e[maxe][3]; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume++][2]=0; } int ss,tt,n,m,fr; int vis[maxv];int lev[maxv]; bool bfs() { for(int i=0;i<maxv;i++) vis[i]=lev[i]=0; queue<int>q; q.push(ss); vis[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(!vis[v]&&e[i][2]>0) { lev[v]=lev[cur]+1; vis[v]=1; q.push(v); } } } return vis[tt]; } int dfs(int u,int minf) { if(u==tt||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(lev[v]==lev[u]+1&&e[i][2]>0) { f=dfs(v,minf<e[i][2]?minf:e[i][2]); e[i][2]-=f;e[i^1][2]+=f; sumf+=f;minf-=f; } } if(!sumf) lev[u]=-1; return sumf; } int dinic() { int sum=0; while(bfs())sum+=dfs(ss,inf); return sum; }; int mapp[maxv][maxv]; int fa[maxv+1]; vector<set<int> >tos(maxv); int find(int x) { if(x==fa[x])return x; else fa[x]=find(fa[x]); return fa[x]; } void read_build() { int aa,bb; for(int j=0;j<m;j++) { scanf("%d%d",&aa,&bb); adde(aa,bb+n,1); mapp[aa][bb]=1; } for(int i=0;i<fr;i++) { scanf("%d%d",&aa,&bb); int xx=find(aa); int yy=find(bb); if(xx!=yy) { fa[xx]=yy; } } for(int i=1;i<=n;i++) { int tx=find(i); for(int es=head[i];es!=-1;es=e[es][1]) { if(es%2==0) tos[tx].insert(e[es][0]-n); } } for(int i=1;i<=n;i++) { int tx=find(i); set<int>::iterator it=tos[tx].begin(); for(;it!=tos[tx].end();it++) { if(mapp[i][*it]==0) { mapp[i][*it]=1; adde(i,(*it)+n,1); } } } for(int i=1;i<=n;i++) { adde(ss,i,1); adde(i+n,tt,1); } /* for(int i=0;i<=tt;i++) for(int j=head[i];j!=-1;j=e[j][1]) { printf("%d->%d:%d\n",i,e[j][0],e[j][2]); }*/ } void init() { nume=0; memset(mapp,0,sizeof(mapp)); ss=0;tt=2*n+1; for(int i=0;i<maxv;i++) { head[i]=-1;fa[i]=i;tos[i].clear(); } } int main() { int T; scanf("%d",&T); for(int ii=1;ii<=T;ii++) { int tx; scanf("%d%d%d",&n,&m,&fr); init(); read_build(); int ans=0; while(dinic()==n) { ans++; for(int i=head[0];i!=-1;i=e[i][1]) { e[i][2]=1; e[i^1][2]=0; } for(int i=head[tt];i!=-1;i=e[i][1]) { e[i^1][2]=1; e[i][2]=0; } } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。