本文共 1940 字，大约阅读时间需要 6 分钟。
题意
n个车牌，长度固定为7，车牌与车牌间的距离为不同字母个数。问所有车牌形成一棵树的最小边权和是多少。
分析
最小生成树模板
#include #include #include #include #include #include #include #include #include #define rep(i,e) for(int i=0;i<(e);i++)#define rep1(i,e) for(int i=1;i<=(e);i++)#define repx(i,x,e) for(int i=(x);i<=(e);i++)#define X first#define Y second#define PB push_back#define MP make_pair#define mset(var,val) memset(var,val,sizeof(var))#define scd(a) scanf("%d",&a)#define scdd(a,b) scanf("%d%d",&a,&b)#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)#define pd(a) printf("%d\n",a)#define scl(a) scanf("%lld",&a)#define scll(a,b) scanf("%lld%lld",&a,&b)#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;typedef long long ll;template void test(T a){cout< < void test(T a,T2 b){cout< <<" "<< void test(T a,T2 b,T3 c){cout< <<" "<<<" "< < inline bool scan_d(T &ret){ char c;int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret = ret*10+(c-'0'); ret*=sgn; return 1;}//const int N = 1e6+10;const int inf = 0x3f3f3f3f;const ll INF = 0x3f3f3f3f3f3f3f3fll;const ll mod = 1000000000;int T;void testcase(){ printf("Case %d:",++T);}const int MAXN = 2500 ;const int MAXM = 250;const double eps = 1e-8;const double PI = acos(-1.0);bool vis[MAXN];int lowc[MAXN];int cost[MAXN][MAXN];int Prim(int n){ int ans=0; mset(vis,false); vis[0]=true; for(int i=1;i lowc[j]){ minc = lowc[j]; p = j; } } if(minc == inf){ return -1; } ans+=minc; vis[p]=true; for(int j=0;j cost[p][j]){ lowc[j] = cost[p][j]; } } } return ans;}char s[MAXN][10];int main() {#ifdef LOCAL freopen("in.txt","r",stdin);#endif // LOCAL int n; while(~scanf("%d",&n)&&n){ for(int i=0;i
转载于:https://www.cnblogs.com/fht-litost/p/9207256.html