POJ -- 1639 [Picnic Planning] K 한도 최소 생 성 트 리

알고리즘 프로 세 스: 1. 이 점 (이하 v0 으로 표시) 을 그림 에서 삭제 하면 m 개의 연결 분량 을 얻 을 수 있 습 니 다.
2. 모든 연결 분량 에 대해 최소 생 성 트 리 를 구하 고 m 개 를 가설 합 니 다.
3. 각 연결 분량 에서 v0 과 연 결 된 가중치 가 가장 작은 변 을 찾 아 v0 과 연결 하면 v0 의 최소 m 도 생 성 트 리 를 얻 을 수 있 습 니 다.
하면, 만약, 만약...  < 그럼 이런 나 무 는 존재 하지 않 습 니 다.
5. k > = m 이면 m + 1 도 최소 생 성 트 리 구축 을 고려 하여 v0 과 연 결 된 현재 트 리 의 가장자리 가 아 닙 니 다.
6. 트 리 에 넣 으 면 링 이 존재 합 니 다. 이 링 에서 v0 과 관련 이 없 는 가중치 의 최대 변 을 삭제 하면 이 변 에 가입 한 최소 생 성 트 리 와 m + 1 을 얻 을 수 있 습 니 다.
7. 상기 6 의 사 이 드 트 리 의 가중치 가 가장 적 으 면 m + 1 도 제한 의 최소 생 성 트 리 입 니 다.
8. k 도 최소 생 성 트 리 가 나타 날 때 까지 5.6.7 을 반복 합 니 다.
 
CODE:

/*K       */
/*
(1):      <=K      
*/
/*AC  ：0ms*/
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#define MAXN 100
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
	int u,v,w,next; 
	bool flag;
}E[200000],E1[20000],E2[20000];
//E[]:    K     
//E1[]:       
//E2[]:  vo     
int head[MAXN],ecnt,vcnt;;
int N,K,cnt,vo,now;
map<string,int>hash;
int p[MAXN];
int pre[MAXN];
bool vis[MAXN];
bool ok;
void Insert(int u,int v,int w)
{
	E[ecnt].u=u;
	E[ecnt].v=v;
	E[ecnt].w=w;
	E[ecnt].flag=true;
	E[ecnt].next=head[u];
	head[u]=ecnt++;
}
int cmp(const void *p1,const void *p2)
{
	return ((struct edge *)p1)->w-((struct edge *)p2)->w;
}
int find_set(int x)
{
	if(x!=p[x])
		p[x]=find_set(p[x]);
	return p[x];
}
void Init()
{
	int i,u,v,w;
	string a,b;
	hash.clear();
	cnt=0;
	for(i=1;i<=N;i++)
	{
		cin>>a>>b>>w;
		if(!hash[a]) hash[a]=++cnt;
		if(!hash[b]) hash[b]=++cnt;
		u=hash[a];v=hash[b];
		E1[i].u=u;E1[i].v=v;
		E1[i].w=w;
	}
	scanf("%d",&K);
	string c="Park";
	vo=hash[c];
	qsort(E1+1,N,sizeof(E1[1]),cmp); 
	/*
	printf("&&&%d
",vo);
	for(i=1;i<=N;i++)
		printf("%d %d %d
",E1[i].u,E1[i].v,E1[i].w);
	printf("
");
	*/
}
void swap(int &a,int &b)
{
	int t;
	if(b==vo)
	{t=a;a=b;b=t;}
}
void Run()
{
	int i,u,v,w;
	now=0;
	for(i=0;i<vcnt;i++)
	{
		u=E2[i].u;
		v=E2[i].v;
		w=E2[i].w;
		int du=find_set(u);
		int dv=find_set(v);
		if(du!=dv)
		{
			E2[i].flag=true;
			now++;
			p[du]=dv;
			Insert(u,v,w);
			Insert(v,u,w); 
		}
	}
}
queue<int>Q;
int bfs(int s,int e,int ith,bool ok)
{
	int i,u,v,w;
	while(!Q.empty()) Q.pop();
	memset(vis,false,sizeof(vis));
	memset(pre,-1,sizeof(pre));
	Q.push(s);
	vis[s]=true;
	while(!Q.empty())
	{
		//printf("&
");
		u=Q.front();Q.pop();
		for(i=head[u];i!=-1;i=E[i].next)
		{
			if(!E[i].flag) continue;//       
			v=E[i].v;
			if(!vis[v])
			{
				pre[v]=i;
				if(v==e) break;
				vis[v]=true;
				Q.push(v);
			}
		}
	}
	int id,Index,res=0;
	u=e;
	while(true)
	{
		//printf("##
");
		id=pre[u];
		//     vo          
		if((E[id].u!=vo&&E[id].v!=vo)&&E[id].w>res)
		{
			res=E[id].w;
			Index=id;
		}
		u=E[id].u;
		if(u==s) break;
	}
	if(ok)
	{
		E[Index].flag=E[Index^1].flag=false;
		Insert(s,e,E2[ith].w);
		Insert(e,s,E2[ith].w);
		E2[ith].flag=true;//     
	}
	return E2[ith].w-res;
}
void ff()
{
	int i,u,v,w,temp;
	int id=-1,res=INF;
	//     vo             
	for(i=0;i<vcnt;i++)
	{
		//printf("**
");
		if(!E2[i].flag)
		{
			temp=bfs(vo,E2[i].v,i,false);
			if(temp<res)
			{
				id=i;
				res=temp;
			}
		}
	}
	if(res>=0) 
	{ok=false;return;}
	bfs(vo,E2[id].v,id,true); 
}
int get_ans()
{
	int res=0,i;
	for(i=0;i<ecnt;i+=2)
	{
		if(E[i].flag)
			res+=E[i].w; 
	}
	return res;
}
void Solve()
{
	int i,u,v,w;
	memset(head,-1,sizeof(head));ecnt=0;
	for(i=1;i<=cnt;i++)
		p[i]=i;
	vcnt=0;
	for(i=1;i<=N;i++)
	{
		u=E1[i].u;
		v=E1[i].v;
		swap(u,v);
		w=E1[i].w;
		if(u==vo||v==vo)
		{
			E2[vcnt].u=u;
			E2[vcnt].v=v;
			E2[vcnt].flag=false;
			E2[vcnt].w=w;
			vcnt++;
			continue;
		}
		int du=find_set(u);
		int dv=find_set(v);
		if(du!=dv)
		{
			p[du]=dv;
			Insert(u,v,w);
			Insert(v,u,w);
		}
	}
	Run();
	/*
	printf("*
");
	for(i=0;i<vcnt;i++)
		printf("%d %d %d
",E2[i].u,E2[i].v,E2[i].w);
	printf("
");
	printf("^%d
",now);
	*/
	//  
	ok=true;
	for(i=now;i<K&&ok;i++)
		ff();
	int ans=get_ans();
	printf("Total miles driven: %d
",ans);
	
}
int main()
{
	//freopen("A.21.dat","r",stdin);
	//freopen("1639.txt","w",stdout);
	while(scanf("%d",&N)!=EOF)
	{
		Init();
		Solve();
	}
return 0;
}
/*

7
Jonesy Park 3
J Jonesy 1
Jonesy James 1
Jonesy Jimmy 1
J Park 10
Park James 10
Jimmy Park 10
4

Total miles driven: 6
*/