P2916 [USACO08NOV] Comforting the Cow

P2916 [USACO08NOV] Cheering up the Cow#

Problem Description#

John has N pastures, numbered from 1 to N. Each pasture contains a cow. There are P roads connecting these pastures, and each road is bidirectional. The j-th road connects pasture 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 removing the roads. John can choose to start his work from any pasture. After visiting all the cows, he needs to return to his starting pasture. Each time he passes pasture i, he must spend Ci time talking to the cow, even if he has already done so before. Note that John needs to talk to the cow in his starting pasture when he leaves and returns. Please calculate which roads John should remove 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 weight of the edges to the time it takes to walk plus the time spent talking to both ends, the selected edges for the minimum spanning tree (according to the example) are the same as the example answer.

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

I told hqx about it, and he found through rigorous reasoning that as long as the weight of the edges is set to twice the time on the road plus the time of the two ends, the sum of the minimum spanning tree plus 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;
}