染色問題：相鄰不能染同一種顏色

最少需要的顏色的數量=最大團點的數量

#include<bits/stdc++.h> using namespace std;#define N 27int n; int mp[N][N]; int ans; int alt[N][N]; int Max[N];bool dfs(int cur,int tot)//cur是s1集合的個數 {if(0==cur){if(tot>ans){ans=tot;return true;}return false;}for(int i=0;i<cur;i++){if( tot+cur-i<=ans )return false;int u=alt[tot][i];if( Max[u]+tot<=ans )return false;int next=0;for(int j=i+1;j<cur;j++)if(mp[u][ alt[tot][j] ])alt[tot+1][next++]=alt[tot][j];if(dfs(next,tot+1)) return 1;}return 0; }int maxclique(void) {ans=0;memset(Max,0,sizeof(Max));for(int i=n-1;i>=0;i--){int cur=0;for(int j=i+1;j<n;j++)if(mp[i][j])alt[1][cur++]=j;//1為s1集合dfs(cur,1);Max[i]=ans;}return ans; }int main() { char s[30];while(scanf("%d",&n),n){ memset(mp,0,sizeof (mp));for(int i=0;i<n;i++){scanf("%s",s);for(int j=2;s[j];j++)mp[i][ s[j]-'A' ]=mp[ s[j]-'A' ][i]=1;}int ans=maxclique();if(ans==1) printf("1 channel needed.\n");else printf("%d channels needed.\n", ans);}return 0; }

?

轉載于:https://www.cnblogs.com/bxd123/p/10388143.html

總結

以上是生活随笔為你收集整理的Channel Allocation HDU1373的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。