本文共 851 字，大约阅读时间需要 2 分钟。

题目

思路

采取正难则反的思想，应用容斥，把题目变为尽量连接不是敌人节点的点，注意，如果连接一个正常点和一个敌人节点，则正常节点会被入侵。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a,b,g;long long ans;int fa[100005];bool yy[100005];struct f{    int x,y,z;} e[100005];int find(int x){    if (x==fa[x]) return x; return fa[x]=find(fa[x]); }void jb(int x,int y,int z){    g++; e[g].x=x; e[g].y=y; e[g].z=z; return;}bool cmp(f a,f b){    return a.z>b.z;}void f(){    int j=1; while (j<=g) {     int xx=find(e[j].x),yyy=find(e[j].y);  if (!(yy[xx]&&yy[yyy]))  {      fa[xx]=yyy;   yy[yyy]=yy[xx]|yy[yyy];   ans-=e[j].z;  }  j++; } return;}int main(){    cin>>b>>a; for (int i=1;i<=b;i++) fa[i]=i; for (int i=1;i<=a;i++) {     int x;  cin>>x;  yy[x]=1; } for (int i=1;i
        
         >x>>y>>z; jb(x,y,z); ans+=z; } sort(e+1,e+g,cmp); f(); cout<