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