題面描述
給定一個n個點萝毛，m條邊的無向圖项阴，其中你在第i個點建立旅游站點的費用為Ci。在這張圖中笆包，任意兩點間不存在節(jié)點數(shù)超過10的簡單路徑环揽。請找到一種費用最小的建立旅游站點的方案，使得每個點要么建立了旅游站點庵佣，要么與它有邊直接相連的點里至少有一個點建立了旅游站點薯演。
輸入格式
第一行包含兩個正整數(shù)n,m(1<=n<=20000,0<=m<=25000)，分別表示點數(shù)和邊數(shù)秧了。
第二行包含n個整數(shù)跨扮，其中第i個數(shù)為Ci(0<=Ci<=10000)，表示在第i個點建立旅游站點的費用验毡。
接下來m行衡创，每行兩個正整數(shù)u,v(1<=u,v<=n)，表示u與v之間連了一條邊晶通，保證沒有重邊璃氢。
輸出格式
輸出一行一個整數(shù)，即最小的總費用狮辽。
樣例數(shù)據(jù)
樣例輸入
3
1 2 3
樣例輸出
1
2
題解
直接dfs暴力查找最優(yōu)解即可一也。中間需判斷到達(dá)一個點后還能否繼續(xù)移動到其它點。如果可以喉脖，則將這條支路上的貢獻(xiàn)一并加入總的答案中椰苟。同時，當(dāng)一個點被到達(dá)后我們需要判斷是否走進了回路树叽。這里可以記錄之前到達(dá)的路徑舆蝴，如果發(fā)現(xiàn)重復(fù)的路徑則說明進入了回路。
這里貼出未剪枝的代碼。
#include<bits/stdc++.h>
#define int long long
#define maxn 200005
#define maxm 200005
using namespace std;
inline char get(){
static char buf[30000],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
struct edge{
int u,v,w,next;
}E[maxm<<1];
int p[maxn],eid;
inline void init(){
for(register int i=0;i<maxn;i++)p[i]=-1;
eid=0;
}
inline void insert(int u,int v,int w){
E[eid].u=u;
E[eid].v=v;
E[eid].w=w;
E[eid].next=p[u];
p[u]=eid++;
}
inline void insert2(int u,int v,int w){
insert(u,v,w);
insert(v,u,w);
}
int n,m,a[maxn],s;
int vis[maxn];
int dfs(int u,int last,int w,int deep){
if(deep>n+5)return w;
w+=a[u];
//cout<<u<<" "<<deep<<endl;
//cout<<u<<" "<<last<<" "<<a[u]<<" "<<w<<endl;
int save=a[u];
a[u]=0;
int ret=0;
for(register int i=p[u];~i;i=E[i].next){
int v=E[i].v;
//cout<<v<<" "<<vis[i]<<endl;
vis[i]=1;
if(v==last && (vis[i] || vis[i ^ 1]))continue;
//cout<<v<<"<>"<<vis[i]<<endl;
ret=max(ret,dfs(v,u,w,deep+1));
vis[i]=0;
}
a[u]=save;
if(ret==0)return w;
return ret;
}
signed main(){
//freopen("1.txt","r",stdin);
init();
n=read(),m=read();
for(register int i=1;i<=n;i++)a[i]=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read();
insert2(u,v,1);
}
s=read();
cout<<dfs(s,-1,0,0);
return 0;
}
