首页 > 其他 > 详细

BZOJ4349 最小树形图

时间:2019-02-12 19:20:15      阅读:102      评论:0      收藏:0      [点我收藏+]

标签:小店   ble   sin   接下来   scanf   fin   后来   truct   bzoj   

据说是一道重题 可以见[JSOI2008]小店购物

同样是最小树形图 可以注意到每个点只要都被打了一次那么接下来都可以使用最小的代价来攻打

那么我们把第一次进行的攻打跑最小树形图即可 注意要建虚点作为起始状态

【最开始想错了 以为必须全打掉才可以用后来的新代价 WA飞以后看题解才明白qaq

技术分享图片
//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 1e20
#define ll long long
#define N 1100
#define M 100100
#define db double
using namespace std;

struct edge{int u,v; db c;}e[M];
int pre[N],id[N],vis[N];
int n,m;db mn[N];
db zlal(int rt)
{
    db res = 0.0;
    while(1)
    {
        for(int i=1;i<=n;i++)    mn[i] = inf;
        for(int i=1;i<=m;i++)
            if(e[i].u != e[i].v && mn[e[i].v]>e[i].c)
            {
                mn[e[i].v] = e[i].c; pre[e[i].v] = e[i].u;
            }
        for(int i=1;i<=n;i++)    if(i!=rt && mn[i]==inf)    return 0;
        int tn = 0,u,v;
        memset(id,0,sizeof(id)); memset(vis,0,sizeof(vis));
        mn[rt] = 0;
        for(int i=1;i<=n;i++)
        {
            res += mn[i]; v=i;
            while(v!=rt && !id[v] && vis[v]!=i)
                vis[v] = i, v = pre[v];
            if(v!=rt && !id[v])
            {
                ++tn;
                for(u=pre[v];u!=v;u=pre[u])
                    id[u] = tn;
                id[v] = tn;
            }
        }
        if(!tn)    break;
        for(int i=1;i<=n;i++)    if(!id[i])
            id[i] = ++tn;
        for(int i=1;i<=m;i++)
        {
            v = e[i].v;
            e[i].u = id[e[i].u];
            e[i].v = id[e[i].v];
            if(e[i].u != e[i].v)
                e[i].c -= mn[v];
        }
        n = tn; rt = id[rt];
    }
    return res;
}
db a[N],cc[N]; int b[N],cnt;
int main()
{
    //int r;    scanf("%d%d%d",&n,&m,&r);
    //for(int i=1;i<=m;i++)    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].c);
    scanf("%d",&n); n++; db ans = 0.0;
    for(int i=1;i<n;i++)
    {
        scanf("%lf%d",&a[i],&b[i]);
        if(b[i]<=0)    continue;// ans+=(b[i]-1)*a[i];
        e[++cnt].u = n, e[cnt].v=i ,cc[i]=e[cnt].c=a[i];
    }
    int k,x,y;db c; scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%lf",&x,&y,&c);
        e[++cnt].u=x; e[cnt].v=y; e[cnt].c=c; cc[y]=min(cc[y],c);
    } m = cnt;
    for(int i=1;i<n;i++)    ans+=(b[i]-1)*cc[i];
    printf("%.2lf\n",zlal(n) +ans);
    return 0;
}
/**
3 
10.00 1
1.80 1 
2.50 2
2
1 3 2.00
3 2 1.50
*/
View Code

 

BZOJ4349 最小树形图

标签:小店   ble   sin   接下来   scanf   fin   后来   truct   bzoj   

原文:https://www.cnblogs.com/hanyuweining/p/10366717.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号