首页 > 代码库 > hust 1045 Task Arrangement II
hust 1045 Task Arrangement II
题目描述
There are N tasks and M resources, each task is asked to use some resources and each resource can only be used by at most one task. You are asked to find the best arrangement to maximum the total number of the compatible tasks.
输入
There are multi test cases. Each case contains a number of lines. The first line is N and M, 1 <= N, M <= 50. In the following N lines, each task contains one line with many integers separated by exactly one space, which specify the required resources. The index of the resources starts from 0.
输出
For each test case, output one line containing the maximum number of the compatible tasks.
样例输入
5 50 3 11 42 103 23 31 00 21 2
样例输出
31
又是一道经典题目，先说说我对这个题的感觉吧！一开始认为是一道二分图匹配的题目，可是怎么弄都不清楚，后来又想是不是网络流的题目，唉！还是做不出来，在后来就直接搜索，肯定超时，怎么办，于是想到是不是最大团，结果还真是，两个没有公共资源的任务便可以连一条边，这样不就是求最大团吗？真的很经典
#include<map>#include<set>#include<stack>#include<queue>#include<cmath>#include<vector>#include<cstdio>#include<string>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define inf 0x0f0f0f0fusing namespace std;const double pi=acos(-1.0);const double eps=1e-8;typedef pair<int,int>pii;vector<int>task[51];void init(int n){ for (int i=0;i<=n;i++) task[i].clear();}struct max_clique{ static const int N=100; bool G[N][N]; int n,Max[N],Alt[N][N],ans; bool DFS(int cur,int tot) { if (cur==0) { if (tot>ans) { ans=tot; return true; } return false; } for (int i=0;i<cur;i++) { if (cur-i+tot<=ans) return false; int u=Alt[tot][i]; if (Max[u]+tot<=ans) return false; int nxt=0; for (int j=i+1;j<cur;j++) if (G[u][Alt[tot][j]]) Alt[tot+1][nxt++]=Alt[tot][j]; if (DFS(nxt,tot+1)) return true; } return false; } int maxclique() { ans=0; memset(Max,0,sizeof(Max)); for (int i=n-1;i>=0;i--)//编号从0开始 { int cur=0; for (int j=i+1;j<n;j++) if (G[i][j]) Alt[1][cur++]=j; DFS(cur,1); Max[i]=ans; } return ans; }};max_clique T;void read(int n){ getchar(); char str[1000],str1[10]; for (int i=0;i<n;i++) { gets(str); int k=0,j=0; int L=strlen(str); while(k<L) { if (str[k]==‘ ‘) { str1[j]=NULL; task[i].push_back(atoi(str1)); j=0; } else { str1[j]=str[k]; j++; } k++; } str1[j]=NULL; task[i].push_back(atoi(str1)); }}void sovle(int n){ bool vis[51]; T.n=n; for (int i=0;i<n;i++) for (int j=0;j<n;j++) T.G[i][j]=1; for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { memset(vis,0,sizeof(vis)); for (int k=0;k<task[i].size();k++) { int v=task[i][k]; vis[v]=true; } bool cut=true; for (int k=0;k<task[j].size();k++) { int v=task[j][k]; if (vis[v]) { cut=false; break; } } if (!cut) T.G[i][j]=0; } }}int main(){ //freopen("in.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { init(n); read(n); sovle(n); printf("%d\n",T.maxclique()); } //fclose(stdin); return 0;}
作者 chensunrise
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。