首页 > 代码库 > LA 3415 (二分图+最大独立集）
LA 3415 (二分图+最大独立集）
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1416
题目大意：一个老师带他的一群学生去旅游。带走的这群学生整体必须满足给出四个条件之一。问最多能带走多少学生。
解题思路：
二分图匹配题。最初我是这样考虑的：符合条件的学生连一条边，求最大匹配*2就行了。
但是问题却没那么简单。最大匹配保证的是多少人被匹配，至于匹配的东西是否有重复，它就不管了。如果简单的最大匹配数*2，那么中间有一些人被匹配了多次，也就是说人多了！
想要得到独立的人数，则必须使用最大独立集做法。
最大独立集的求法很简单：最大匹配的建图方式反过来！意思说完全不符合条件的才连边，在这题里，就是4个条件都不符合要求的学生连一条边。
然后求最大匹配数，ans=n-match/2。
注意这里为啥要除以2，因为你在建图的时候肯定图方便，用了两层for(1..n)判断i和j然后addedge了吧，这样就成了无向图了。
而Hungry是针对有向图的，所以match数成了原来的2倍，所以要除以2。
二分图中使用链式前向星也是挺好的。
#include "string"#include "cstdio"#include "cstring"#include "iostream"using namespace std;#define maxn 505int n,head[maxn],tol,link[maxn];bool vis[maxn];struct Edge{ int next,to;}e[maxn*maxn];struct person{ int h; char sex; string music,sport;}p[505];void addedge(int u,int v){ e[tol].to=v; e[tol].next=head[u]; head[u]=tol++;}int abs(int x) {return x<0?-x:x;}bool judge(person a,person b){ if(abs(a.h-b.h)<=40&&a.sex!=b.sex&&a.music==b.music&&a.sport!=b.sport) return true; else return false;}bool dfs(int u){ for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to; if(vis[v]) continue; vis[v]=true; if(!link[v]||dfs(link[v])) { link[v]=u; return true; } } return false;}int main(){ ios::sync_with_stdio(false); int T; cin>>T; while(T--) { memset(link,0,sizeof(link)); memset(head,-1,sizeof(head)); tol=0; cin>>n; for(int i=1;i<=n;i++) { cin>>p[i].h>>p[i].sex>>p[i].music>>p[i].sport; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j&&judge(p[i],p[j])) {addedge(i,j);} int match=0; for(int i=1;i<=n;i++) { memset(vis,false,sizeof(vis)); if(dfs(i)) match++; } printf("%d\n",n-match/2); }}
| 2815370 | neopenx | UVALive 3415 | Accepted | 0 KB | 233 ms | C++ 4.5.3 | 1464 B | 2014-10-04 21:22:11 |
LA 3415 (二分图+最大独立集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。