题解：P9614 [CERC2019] Ponk Warshall

Charles_with_wkc · 2026-03-06 23:14:00 · 题解

题意

题目要求每次交换两个字符，最少多少次交换使第一个字符串变成第二个字符串。

思路

我们考虑图论建模，如果 c_1 要变成 c_2 我们就考虑构建一条 c_1 到 c_2 的有向边，最后判环统计结果。

因为字符十分少，我们考虑用数组。

统计结果时，一元环，二元环，三元环，四元环，它们的花费分别是 0 次，1 次，2 次，3 次。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=10;
int a[N][N];
int ans,tmp;
string s1,s2;
int zh(char c){
    if(c=='A') return 1;
    if(c=='C') return 2;
    if(c=='G') return 3;
    if(c=='T') return 4;
    return 5;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>s1>>s2;
    for(int i=1;i<=s1.size();i++){
        if(s1[i-1]!=s2[i-1]) a[zh(s1[i-1])][zh(s2[i-1])]++;
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            if(!(a[i][j]&&a[j][i])) continue;
            tmp=min({a[i][j],a[j][i]});
            a[i][j]-=tmp;
            a[j][i]-=tmp;
            ans+=tmp*1;
        }
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            if(!a[i][j]) continue;
            for(int k=1;k<=4;k++){
                if(!(a[j][k]&&a[k][i])) continue;
                tmp=min({a[i][j],a[j][k],a[k][i]});
                a[i][j]-=tmp;
                a[j][k]-=tmp;
                a[k][i]-=tmp;
                ans+=tmp*2;
            }
        }
    } 
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            if(!a[i][j]) continue;
            for(int k=1;k<=4;k++){
                if(!a[j][k]) continue;
                for(int z=1;z<=4;z++){
                    if(!(a[k][z]&&a[z][i])) continue;
                    tmp=min({a[i][j],a[j][k],a[k][z],a[z][i]});
                    a[i][j]-=tmp;
                    a[j][k]-=tmp;
                    a[k][z]-=tmp;
                    a[z][i]-=tmp;
                    ans+=tmp*3;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}