战争
【问题描述】
在2240年，一场巨大的战争在地球联合力量（EAF）与火星联盟(MF)之间展开。至今，双方势均力敌。因最近的一次经济危机，资源紧缺，EAF将被MF勒要更多领土。为此，EAF决定采取战争以来最重要的行动：发动对分散在MF上各处的基地进行同时攻击。EAF的力量大都是mechs——大型两足跛行车，有飞行功能。
典型的MF基地概况如下：构成基地的房屋地跨一到两块领土。每块领土被保护塔产生的穿不透的能量层所笼罩，以免于外来袭击。这些保护塔围绕在领土周围起保护作用。
每座保护塔通过建造在地面上的水道与至少一座塔相联系。当那些相联系的塔围成一圈，它们产生能量层。否则能量层消失。
MF知道如果能量层消失，基地将很容易被EAF的力量侵占，因此，被水道相连的两座塔保护水道免受军事袭击。每座塔有防御功能，能拆卸指定数量的mechs，每个水道在坍塌之前能解决特定数量敌方mechs的袭击。这个数量由水道连接的两塔能拆卸的总数量决定。两座塔不能被一个以上的水道相连。
但是，袭击塔一边的水道不减少塔在另一边能拆卸的mechs的数量。因为这次行动是突袭，所有的对水道的袭击都必须同时，所有水道同时坍塌瓦解。
所有能量层必须废除才算毁灭了一个MF基地。破坏所有水道能达此目的，但也将需要很多mechs 牺牲。EAF只有很少的力量花费了，必须最有效率地部署mechs。
你被赋予这任务，写程序：使EAF胜利。给定一幅保护塔的曲线图，决定哪些水道要被破坏，来使所有能量层消失，要求战斗中牺牲最少的mechs。
【输入格式】
第一行为一个整数m，2 < m <= 100，代表塔的数量。
以下2m行，对于每个塔都有两行输入：
◎一行包含三个正整数i(0 <= i <= m-1)，ui(1 <= ui <= 50)，ci(1 <= ci <= m-1)：每个塔的身份标识、可以摧毁的mechs的数量和与它相连的河道的数量。两个整数间用一个空格隔开。
◎一行包含ci个不同的正整数，代表和塔i连接的塔。一个塔不能连接到它自己，两个整数间用一个空格隔开。
该防御体系至少能够生成一个能量层。 不一定所有的塔连通。
【输出格式】
一行一个整数，代表EAF摧毁所有能量层所需要消耗的最少数量的mechs。
【输入样例】
3
0 1 2
1 2
1 2 2
0 2
2 3 2
0 1
【输出样例】
3
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int c,m,l,fa[];
int a[],b[],d[],z[];
long tot=,total=;
int find(int x){
if (fa[x]==x) return x; else return fa[x]=find(fa[x]);
}
void sort(int l,int r){
int i=l,j=r,mid=d[(l+r)/];
while (i<=j){
while (d[i]>mid) i++;
while (d[j]<mid) j--;
if (i<=j){
swap(a[i],a[j]);
swap(b[i],b[j]);
swap(d[i],d[j]);
i++;j--;
}}
if (i<r)sort(i,r);
if (l<j)sort(l,j);
}
void add(int x,int y,int z){
a[++tot]=x;
b[tot]=z;
d[tot]=y;
}
int main(){
int i,j,s,t,n,x,y; freopen("warfare.in","r",stdin);
freopen("warfare.out","w",stdout); scanf("%d",&n);
for (i=;i<n;i++){
scanf("%d%d%d",&m,&l,&c);
for (j=;j<c;j++){
scanf("%d",&s);
add(m,l,s);
total=total+l;
}
z[m]=l;
}
for (i=;i<=tot;i++) fa[i]=i;
sort(,tot); for (i=;i<=tot;i++){
x=find(a[i]);
y=find(b[i]);
if (x!=y){
fa[x]=y;
total=total-(z[a[i]]+z[b[i]]);
}
}
printf("%d",total);
return ;
}
代码
首先先说一下这一题，这是一题很裸的最大生成树，应该算是在初学时还不错的一题吧，依旧是根据最大生成树的原理很容易YY的 感觉打这题不太好打的地方，其实也是在我学最大生成树时最不理解的地方，应该是什么时候开始加边，什么时候不加边 这个问题应该是让我想了很久，之后再学习并查集的原理之后，打了一题并查集的裸题才有所体会（这一点也让我倍感在学习新的知识的时候，刷裸题的重要性啊），貌似是在看到并查集的第二个步骤：合并，的时候有种很像是明白也什么的样子 之后就意识到，条件就是判断是否已构成一棵树，讲的很白一点就是，判断某条边的两个端点是否有同一个祖先，如果没有，那么就合并，并用总的边权值减去该边（当然这是因题来说） 再啰嗦一下吧，自己还是很不注意循环的起始0.，唔。。这个不好的习惯要改嗯，其实这里也可以用sort，定义一个数组就可以实现= =自己懒得改了，下次有机会再用吧 这题对我来说还是蛮有意义的，是本蒟蒻学习图论的一个好的开始嗯，之前没有学的东西也是时候该认真学~\(≧▽≦)/~啦啦啦.....打算月考完，继续学习图论，把最短路问题学完，再把队列部分过一遍，之后还是继续刷长乐的题，复习复习算法，碰到新的东西趁机学一学嗯 = =还是没忍住等到月考之后再发题解orz....祝第一次月考顺利