求一个无向图的最小环, 建立模型比较简单, 输入数据的格式比较难受, 我采用了DFS,
/**//*
ID: lorelei3
TASK: fence6
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int N = 105;
const int NS = 10;
const int MAX = 9999999;
enum
{N1, N2, YES, NO, FINISH, ERROR};
struct Fence{
int length;
int n1s, n2s;
int n1[NS], n2[NS];
bool visited;
Fence(){
length=0, n1s=0, n2s=0;
memset(n1, 0, sizeof(n1));
memset(n2, 0, sizeof(n2));
visited=false;
}
};
Fence fences[N];
int ans = MAX;
inline int dir(int k, int ni){
int i;
for(i=0; i<fences[k].n1s; ++i)
if(fences[k].n1[i] == ni)
return N1;
for(i=0; i<fences[k].n2s; ++i)
if(fences[k].n2[i] == ni)
return N2;
return ERROR;
}
inline int check(int k, int op){
if(op == N2){
int t=0;
for(int i=0; i<fences[k].n1s; ++i)
if(fences[fences[k].n1[i]].visited)
t++;
if(t==0)
return YES;
else if(t==1)
return FINISH;
else if(t>1)
return NO;
}else{
int t=0;
for(int i=0; i<fences[k].n2s; ++i)
if(fences[fences[k].n2[i]].visited)
t++;
if(t==0)
return YES;
else if(t==1)
return FINISH;
else if(t>1)
return NO;
}
return ERROR;
}
void dfs(int k, int sum, int ni){
if(sum>ans)
return;
fences[k].visited=true;
int sel = check(k, ni);
if(sel == FINISH){
if(sum<ans)
ans = sum;
fences[k].visited=false;
return;
}else if(sel == NO){
fences[k].visited=false;
return;
}else{
if(ni == N2){
for(int i=0; i<fences[k].n1s; ++i){
int t = fences[k].n1[i];
if(!fences[t].visited)
dfs(t, sum+fences[t].length, dir(t,k));
}
}else{
for(int i=0; i<fences[k].n2s; ++i){
int t = fences[k].n2[i];
if(!fences[t].visited)
dfs(t, sum+fences[t].length, dir(t,k));
}
}
fences[k].visited=false;
}
}
int n, s, Ls, N1s, N2s;
int main(){
int i,j;
ifstream fin("fence6.in");
ofstream fout("fence6.out");
fin>>n;
for(i=0; i<n; ++i){
fin>>s>>Ls>>N1s>>N2s;
fences[s].length=Ls;
fences[s].n1s = N1s;
fences[s].n2s = N2s;
for(j=0; j<N1s; ++j)
fin>>fences[s].n1[j];
for(j=0; j<N2s; ++j)
fin>>fences[s].n2[j];
}
for(i=1; i<=n; ++i){
dfs(i, fences[i].length, N1);
dfs(i, fences[i].length, N2);
}
fout<<ans<<endl;
return 0;
}
posted on 2011-01-23 09:48
小阮 阅读(460)
评论(0) 编辑 收藏 引用 所属分类:
USACO