P2916 [USACO08NOV] Cheering up the Cow

P2916 [USACO08NOV] Cheering up the Cow#

Problem Description#

John has N pastures, numbered from 1 to N. Each pasture is home to a cow. There are P roads connecting these pastures, and each road is bidirectional. The j-th road connects pastures Sj and Ej, and it takes Lj time to travel on it. There is at most one road between any two pastures. John plans to remove as many roads as possible while keeping all the pastures connected.

John knows that the cows will be very sad after the roads are removed, so he plans to cheer them up after demolishing the roads. John can choose to start his work from any pasture. After visiting all the cows, he must return to his starting point. Each time he passes by pasture i, he must spend Ci time talking to the cow, even if he has already done so before. Note that John must also talk to the cow in his starting pasture when he leaves and returns. Please calculate which roads John should remove in order to minimize the total time spent cheering up the cows.

Input/Output Format#

Input:

* Line 1: Two space-separated integers: N and P

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..N+P+1: Line N+j+1 contains three space-separated integers: S_j, E_j, and L_j

Output:

* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your sleeping-pasture)

Input/Output Example#

Input Example #1:

Output Example #1:

Explanation#

   +-(15)-+ 
  /        \ 
 /          \ 
1-(5)-2-(5)-3-(6)--5 
   \   /(17)  / 
(12)\ /      /(12) 
     4------+ 

Keep these paths: 
1-(5)-2-(5)-3      5 
       \          / 
    (12)\        /(12) 
        *4------+

Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2, 3, 2, 1, 2, 4 yielding a total time of 176 before going back to sleep.

Approach#

I found that if I set the edge weight to the walking time plus the time spent talking to both ends, the selected edges for the minimum spanning tree (as shown in the example) are the same as the example answer.

So I plan to use this method to find which edges to select and then use DFS to calculate the total time.

I told hqx about this, and he found through rigorous reasoning that as long as the edge weight is set to twice the time on the road plus the time at both ends, the sum of the minimum spanning tree and the minimum talking time of one point is the shortest total time.

The reason is that each edge will be passed twice (observe the example / create data), consuming the time of both endpoints. The starting point will be counted one more time.

HQX is awesome!

CODE#

#include<cstdio>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int MAXN=1000000+5,INF=0x3f3f3f3f;

int n,p;
int c[10005];

struct tu
{	
	struct edge
	{
		int p1,p2,w,a;
		friend bool operator <(edge x,edge y)
		{
			return x.a<y.a;
		}
	} b[MAXN];
	
	
	int newpe;
	int head[MAXN];
	int fa[MAXN];
	bool v[MAXN];
	
	void insert(int p1,int p2,int w)
	{
		b[++newpe].p1=p1;
		b[newpe].p2=p2;
		b[newpe].w=w;
		b[newpe].a=2*b[newpe].w+c[p1]+c[p2];
	}
	
	int zxscs(void)//最小生成树（原谅我不会打克鲁斯卡尔）
	{
		sort(b+1,b+1+newpe);
		for(int i=1;i<=n;++i)
		{
			fa[i]=i;
		}
		int cnt=0;
		int tot=0;
		for(int i=1;i<=newpe;++i)
		{
			if(doFind(b[i].p1)!=doFind(b[i].p2))
			{
				++cnt;
				tot+=b[i].a;
				doUnion(b[i].p1,b[i].p2);
			}
			if(cnt==n-1)
			{
				return tot;
			}
		}
		return 0;
	}
	
	void doUnion(int x,int y)
	{
		x=doFind(x);
		y=doFind(y);
		fa[x]=y;
	}
	
	int doFind(int x)
	{
		if(fa[x]==x)return x;
		else return fa[x]=doFind(fa[x]);
	}
	
} mp;
int main(void)
{
	scanf("%d%d",&n,&p);
	int minc=INF;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",c+i);
		minc=min(c[i],minc);
	}
	
	for(int i=1;i<=p;++i)
	{
		int p1,p2,w;
		scanf("%d%d%d",&p1,&p2,&w);
		mp.insert(p1,p2,w);
	}
	int ans;
	ans=mp.zxscs();
	ans+=minc;
	printf("%d\n",ans);
	return 0;
}