TIOJ 1528 一字千金 [Tree]

poao899    4420K    6666MS    G++     2.34K     2010-03-29 13:51:35                          .

本篇全部都是雷(?





































阿思：就把他想成一棵樹多了8條邊，然後去枚舉就好了

說實話也不好枚舉orz

一開始很直覺的2^8= 256的枚舉

可以想一下以下這組測資

3 3
10 100 10
1 2
2 3
1 3

答案應該是100

但是3^8= 6561太大了會TLE



而且還有一組測資

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

答案絕對是10

然後下面那組真的是我自己的問題了orz

8 9
6 3 5 2 5 3 1 4
1 2
2 4
4 5
6 4
4 8
5 7
3 5
2 6
7 8

答案是18



所以就變成2^8 *(O(e)檢查 + O(v)DP)

//*******************************

#include<stdio.h>
long long dp[50100][2], max;
int deter[50100], speCnt, n, m, val[50100], a, b, ra, rb;
int root[50100], fa[50100];
int find(int a){return root[a]==a? a: root[a]=find(root[a]);}
//0= no  1= 一定要  2= 一定不能
struct edge{
    int i, j;
    edge *next;
}e[100100], spe[10], *p, *v[50100];
void dfs(int n){
    bool can= 1;
    dp[n][0]= dp[n][1]= 0;
    for(edge *ptr=v[n]; ptr; ptr=ptr->next){
        if(fa[n]== ptr->j)continue;
        fa[ptr->j]= n;
        dfs(ptr->j);
        if(deter[ptr->j]== 1)
            can= 0;
    }
    if(deter[n]!= 2&& can){
        dp[n][1]= val[n];
        for(edge *ptr=v[n]; ptr; ptr=ptr->next){
            if(fa[n]== ptr->j)continue;
            dp[n][1]+= dp[ptr->j][0];
        }
    }if(deter[n]!=1){
        for(edge *ptr=v[n]; ptr; ptr=ptr->next){
            if(fa[n]== ptr->j)continue;
            if(deter[ptr->j]==2)
                dp[n][0]+= dp[ptr->j][0];
            else if(deter[ptr->j]==1)
                dp[n][0]+= dp[ptr->j][1];
            else dp[n][0]+= dp[ptr->j][0]>dp[ptr->j][1]? dp[ptr->j][0]: dp[ptr->j][1];
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        root[i]= i;
        scanf("%d", val+i);
    }
    for(int i=0; i<m; i++){
        scanf("%d%d", &a, &b);
        ra= find(a);
        rb= find(b);
        if(ra==rb){
            spe[speCnt].i=a; spe[speCnt].j=b;
            speCnt++;
        }else{
            e[i].i=a; e[i].j=b;
            p=v[a]; v[a]=&e[i]; e[i].next=p;
            e[i+m].i=b; e[i+m].j=a;
            p=v[b]; v[b]=&e[i+m]; e[i+m].next=p;
            root[rb]= ra;
        }
    }
   
    int ii= 1<<speCnt;
    for(int i=0; i<ii; i++){
        //init
        bool can= 1;
        for(int j=1; j<=n; j++)
            fa[j]=j;
        for(int j=0; can&& j<speCnt; j++){
            if(i& (1<<j)){
                deter[spe[j].i]= 2;
                deter[spe[j].j]= 0;
            }else{
                deter[spe[j].i]= 1;
                deter[spe[j].j]= 2;
            }
        }
        for(int i=0; can&& i<m; i++)
            if(deter[e[i].i]== 1&& deter[e[i].j]== 1)
                can=0;
        for(int i=0; can&& i<speCnt; i++)
            if(deter[spe[i].i]== 1&& deter[spe[i].j]== 1)
                can=0;
        if(!can)continue;
        dfs(root[1]);
        for(int j=0; j<2; j++)
            if(dp[root[1]][j]> max)
                max=dp[root[1]][j];
    }

    printf("%I64d\n",max);
}