题解 P1340 【兽径管理】

· · 题解

109ms，最快的了吧

题意肯定是求最小生成树了，问题在于怎样减少时间消耗。

主要思路是逆序求解，因为这样可以尽可能地减少使用Kruskal的次数，时间复杂度自然就降下来了

每次Kruskal记录用到的边，如果(每一周)删掉了一条用到的边，那自然需要重新求一遍最小生成树；如果没用到，那就不用求了，直接赋值为上一个结果。

如果有一周出现了-1，那它继续删边肯定更不联通了，所以之后所有答案都是-1，break就好

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205,M=6005;

int n,w,Enum,H[M<<1],fa[N];
long long Ans[M];
bool use[M<<1],cannot[M<<1];//use:记录最近一次求最小生成树用到的边   cannot[ i ]:i这条边不能再用了(已删)
struct Edge
{
    int fr,to,nxt,val,id;
    bool operator <(const Edge &a)const
    {
        return val<a.val;
    }
}e[M<<1];

int read()
{
    int now=0;bool f=false;char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar();
    return f?-now:now;
}

void AddEdge(int u,int v,int w)
{
    e[++Enum].to = v;
    e[Enum].fr = u;
    e[Enum].nxt = H[u];
    e[Enum].val = w;
    H[u] = Enum;
}

int Find(int x)
{
    return x==fa[x]?x:fa[x]=Find(fa[x]);
}

long long Kruskal()
{
    memset(use,0,sizeof use);
    for(int i=1;i<=n;i++)
      fa[i]=i;
    int k=0;
    long long tot=0;
    for(int i=1;i<=Enum;i++)
    {
        if(cannot[e[i].id]) continue;
        int r1=Find(e[i].fr),r2=Find(e[i].to);
        if(r1!=r2)
        {
            ++k;tot+=e[i].val;
            use[e[i].id]=1;//printf("use:%d\n",e[i].id);
            fa[r1]=r2;
        }
        if(k==n-1)
          break;
    }
    return k==n-1?tot:-1;
}

int main()
{
    n=read(),w=read();
    for(int a,b,c,i=1;i<=w;i++)
//      Fr[i]=read(),To[i]=read),Val[i]=read();
      a=read(),b=read(),c=read(),AddEdge(a,b,c),e[i].id=i;
    sort(e+1,e+Enum+1);
    Ans[w]=Kruskal();
    for(int i=w-1;i;i--)
    {
        cannot[i+1]=1;//printf("cannot:%d\n",i+1);
        if(use[i+1])
          Ans[i]=Kruskal();//printf("OK\n");
        else
          Ans[i]=Ans[i+1];
        if(Ans[i]==-1)//不连通，那之后的肯定也不连通 
        {
            for(int j=1;j<i;j++)
              Ans[j]=-1;
            break;
        }
    }
    for(int i=1;i<=w;i++)
      printf("%lld\n",Ans[i]);
    return 0;
}