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);
}
沒有留言:
張貼留言