首页 > ACM题库 > HDU-杭电 > HDU 4005-The war-动态规划-[解题报告]HOJ
2015
04-14

HDU 4005-The war-动态规划-[解题报告]HOJ

The war

问题描述 :

In the war, the intelligence about the enemy is very important. Now, our troop has mastered the situation of the enemy’s war zones, and known that these war zones can communicate to each other directly or indirectly through the network. We also know the enemy is going to build a new communication line to strengthen their communication network. Our task is to destroy their communication network, so that some of their war zones can’t communicate. Each line has its "cost of destroy". If we want to destroy a line, we must spend the "cost of destroy" of this line. We want to finish this task using the least cost, but our enemy is very clever. Now, we know the network they have already built, but we know nothing about the new line which our enemy is going to build. In this condition, your task is to find the minimum cost that no matter where our enemy builds the new line, you can destroy it using the fixed money. Please give the minimum cost. For efficiency, we can only destroy one communication line.

输入:

The input contains several cases. For each cases, the first line contains two positive integers n, m (1<=n<=10000, 0<=m<=100000) standing for the number of the enemy’s war zones (numbered from 1 to n), and the number of lines that our enemy has already build. Then m lines follow. For each line there are three positive integer a, b, c (1<=a, b<=n, 1<=c<=100000), meaning between war zone A and war zone B there is a communication line with the "cost of destroy " c.

输出:

The input contains several cases. For each cases, the first line contains two positive integers n, m (1<=n<=10000, 0<=m<=100000) standing for the number of the enemy’s war zones (numbered from 1 to n), and the number of lines that our enemy has already build. Then m lines follow. For each line there are three positive integer a, b, c (1<=a, b<=n, 1<=c<=100000), meaning between war zone A and war zone B there is a communication line with the "cost of destroy " c.

样例输入:

3 2
1 2 1
2 3 2
4 3
1 2 1
1 3 2
1 4 3

样例输出:

-1
3

Hint
For the second sample input: our enemy may build line 2 to 3, 2 to 4, 3 to 4. If they build line 2 to 3, we will destroy line 1 to 4, cost 3. If they build line 2 to 4, we will destroy line 1 to 3, cost 2. If they build line 3 to 4, we will destroy line 1 to 2, cost 1. So, if we want to make sure that we can destroy successfully, the minimum cost is 3.

边双联通分量(有重边)+树上DP

#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
#define N 20100
#define M 200100
#define inf 100000000
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int head1[N],head2[N],cnt,scc,Min;
int dfn[N],low[N],belong[N];
int dp[N];
stack<int>sta;
struct Edge{
    int v,w,next;
}edge[M*4];

void addedge(int u,int v,int w,int *head){
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].w=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void init(int n){
    memset(head1,-1,sizeof(head1));
    memset(head2,-1,sizeof(head2));
    memset(dfn,0,sizeof(dfn));
    for(int i=1;i<=n;i++)dp[i]=inf;
    cnt=scc=0;
}
void DP(int u,int fa){
    int i;
    for(i=head2[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v!=fa){
            DP(v,u);
            dp[v]=min(dp[v],edge[i].w);
            if(dp[u]>dp[v]){
                Min=min(Min,dp[u]);
                dp[u]=dp[v];
            }
            else
                Min=min(Min,dp[v]);
        }
    }
}
void tarjan(int u,int fa){
    int i,flag=1;
    dfn[u]=low[u]=dfn[fa]+1;
    sta.push(u);
    for(i=head1[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa && flag){
            flag=0;
            continue;
        }
        if(dfn[v]==0){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        scc++;
        while(1){
            int tem=sta.top();
            sta.pop();
            belong[tem]=scc;
            if(tem==u)break;
        }
    }
}
int main(){
    int i,n,m;
    int u,v,w;
    while(scanf("%d %d",&n,&m)==2){
        init(n);
        for(i=1;i<=m;i++){
            scanf("%d %d %d",&u,&v,&w);
            addedge(u,v,w,head1);
        }
        for(i=1;i<=n;i++)
            if(dfn[i]==0)
                tarjan(1,0);
        if(scc==1){
            printf("-1\n");
            continue;
        }
        int last=cnt,whi;
        Min=inf;
        for(i=0;i<last;i+=2){
            if(belong[edge[i].v]!=belong[edge[i^1].v]){
                addedge(belong[edge[i].v],belong[edge[i^1].v],edge[i].w,head2);
                if(edge[i].w<Min){
                    whi=i;
                    Min=edge[i].w;
                }
            }
        }
        Min=inf;
        DP(belong[edge[whi].v],belong[edge[whi^1].v]);
        DP(belong[edge[whi^1].v],belong[edge[whi].v]);
        if(Min==inf)printf("-1\n");
        else printf("%d\n",Min);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/8065692


  1. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  2. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  3. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  4. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  5. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  6. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  7. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  8. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  9. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  10. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  11. 民间解释‘孝’:养只狗,狗还知道’忠’主人呢,话虽浅白,确讲到了’孝’的实质,中国孔孟那一套,子女就是狗,养了要’孝顺’主子啊,朝庭的官就是’父母’,要’孝忠’父母啊,’不忠不孝’,父母可杀子女,孔孟那一套的’人性’就是弱肉强食,所以民间百姓谈到’不孝’

  12. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  13. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  14. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  15. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  16. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  17. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  18. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  19. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  20. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  21. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  22. 原因2:楼梯口一般是像门一样,垂直于地面,如果是在地面上做个口子出来,首先浪费地面面积,其次每次上楼有个人头从地面冒出来多诡异,最后就算真是从地面出来,也得在上面装个护栏防止人掉下去吧,可是

  23. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  24. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  25. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环