Code Names

題意：

如果一個字符串通過交換兩個位置可以得到另一個字符串（也就是兩個字符串只有兩個位置不一樣且為交換關(guān)系），我們稱這兩個字符串為替代關(guān)系。
現(xiàn)在給出n個字符串，求一個集合，使得集合內(nèi)的字符串均不是交換關(guān)系，且使得這個集合最大

題解：

現(xiàn)在給每個字符串一個編號
如果兩個字符串i和j成替代關(guān)系，我們就從i到j(luò)連一條線
這樣將n個字符串互相連線，我們就得到一個圖，接下來該怎么辦?
我們知道連線的字符串是不能在一個集合里的
我們將左右側(cè)都為n個字符串，根據(jù)關(guān)系連線，得到下圖（紫色線）

這是個二分圖，我們在這個二分圖上跑最大二分匹配即可，跑出來的結(jié)果m就是不能匹配的數(shù)量，最大獨立集數(shù)就是n ? m，
（注意，我們一開始令ans=n*2，讓ans減去m，最后除以2是答案）
補充一些關(guān)系：
獨立集：圖中兩點不相鄰就是圖的一個獨立集
最大獨立集 = n - 最大匹配
最大匹配 = 最小點覆蓋
最大獨立集 = n - 最小點覆蓋
最大團 = 補圖的最大獨立集
最大獨立集 = 補圖的最大團

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=6e2+9; string a[maxn]; int ans=0; bool vis[maxn]; int edge[maxn][maxn]; int fa[maxn]; int n; bool find(int x){if(vis[x])return 0;vis[x]=1;for(int i=1;i<=n;i++){if(edge[x][i]){if(fa[i]==0||find(fa[i])){fa[i]=x;return 1;}}} return 0; } int main() {cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int len=a[1].length();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int num=0;for(int k=0;k<len;k++){if(a[i][k]!=a[j][k])num++;}if(num==2)edge[i][j]=1;}}ans=n*2;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans-=find(i); }cout<<ans/2; }

總結(jié)

以上是生活随笔為你收集整理的Code Names的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。