洛谷三月月赛 C

呵呵呵呵，这个sb题做了好久，然并卵，还是不对。

挖坑++

然而我感觉我做的对了，偷瞄了一下题解应该没什么问题。

这个题有n个点，n条边，所以是个基环树（我也不知道是不是这个名）

要每个点有联通，就是一个n个点的环，要是答案最小，那么我们就要保留下一些最大的链

现在我们考虑，因为一个点只有一个入度（n-1条边的话是一个严格从根节点单向向外的树），现在多了一个边，所以多了形成一个环

那先现在这个东西（基环树）就是一个环外面挂着一些严格向外延展的子树。

所以先考虑子树，对于每一个节点，贪心的保留一个权值最大的边连的儿子保留，其他的切掉（这里说的切掉是指重建），（这一步做完之后出来的东西就类似于树链剖分出来的重链）

再来考虑环，与环相连的子树，选择切掉，那么环是不用动的，选择不切，那么在环上对应的下条边是要切掉的。（这里打一个标记，判断切没切，然后，没切的话要找环上最小的边切开）

需要注意的是，可以不止一个基环树233333

 #include<bits/stdc++.h>

 #define N 100005

 #define LL long long

 #define inf 1LL<<60

 using namespace std;

 inline LL ra()

 {

     LL x=,f=; char ch=getchar();

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 struct edge{

     int to,next; LL v;

 }e[N];

 int head[N],cnt,n,start,d[N];

 int top,ind,q[N],low[N],dfn[N],size[N],num,belong[N];

 LL ans,sum,f[N],del,cst[N];

 bool vis[N],cut,inq[N],can[N];

 void insert(int x, int y, LL v)

 {

     e[++cnt].next=head[x]; e[cnt].to=y; e[cnt].v=v; head[x]=cnt;

 }

 void tarjan(int x)

 {

     dfn[x]=low[x]=++ind;

     q[++top]=x; inq[x]=;

     for (int i=head[x];i;i=e[i].next)

         if (!dfn[e[i].to])

         {

             tarjan(e[i].to);

             low[x]=min(low[e[i].to],low[x]);

         }

         else if (inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);

     if (low[x]==dfn[x])

     {

         ++num;

         int now=-;

         while (now!=x)

         {

             now=q[top--];

             belong[now]=num;

             size[num]++;

             inq[now]=;

         }

     }

 }

 void get_cost(int x)

 {

     can[x]=;

     for (int i=head[x];i;i=e[i].next)

     {

         if (vis[e[i].to]) cst[x]=e[i].v;

         if (e[i].to==start || !vis[e[i].to]) continue;

         get_cost(e[i].to);

     }

 }

 void solve_son(int x)

 {

     LL son_sum=,son_mx=;

     for (int i=head[x];i;i=e[i].next)

     {

         son_sum+=e[i].v,son_mx=max(son_mx,e[i].v);

         f[x]+=f[e[i].to];

         solve_son(e[i].to);

     }

     f[x]+=son_sum-son_mx;

 }

 void dfs(int x)

 {

     LL son_del=-inf; can[x]=;

     for (int i=head[x];i;i=e[i].next)

     {

         son_del=max(son_del,-cst[x]);

         if (e[i].to==start) continue;

         if (vis[e[i].to]) dfs(e[i].to);

         else

         {

             solve_son(e[i].to);

             ans+=f[e[i].to]+e[i].v;

             son_del=max(son_del,e[i].v-cst[x]);

         }

     }

     if (son_del>) cut=,ans-=son_del; else del=max(del,son_del);

 }

 int main()

 {

     n=ra();

     for (int i=; i<=n; i++)

     {

         int x=ra();

         LL v=(LL)ra();

         if (x==i) ans+=v; else insert(x,i,v);

     }

     for (int i=; i<=n; i++)

         if (!dfn[i]) tarjan(i);

     int hehe=;

     bool flag=;

     for (int i=; i<=n; i++)

         if (size[belong[i]]>)

         {

             if (hehe && hehe!=belong[i]) flag=;

             hehe=belong[i];

             vis[i]=;

         }

     for (int i=; i<=n; i++)

         if (!vis[i]) {flag=; break;}

     if (!flag)

     {

         cout<<""<<endl;

         return ;

     }

     for (int i=; i<=n; i++)

         if (vis[i] && !can[i])

         {

             start=i;

             get_cost(i);

         }

     memset(can,,sizeof(can));

     for (int i=; i<=n; i++)

         if (vis[i] && !can[i])

         {

             cut=; del=-inf;

             start=i; dfs(i);

             if (!cut) ans-=del;

         }

 //    for (int i=1; i<=n; i++) printf("%d ",f[i]);

     cout<<ans<<endl;

     return ;

 }

巴特西

洛谷三月月赛 C

最新文章

热门文章

巴特西

洛谷 三月月赛 C

最新文章

热门文章

洛谷三月月赛 C