USACO/agrinet

来自NOCOW

[编辑] 分析

这个问题需要找出所给图的最小生成树。我们使用这样的算法：在每一步，将不在树中的长度最小的边加入树中。

由于树的尺寸足够小，我们不需要任何复杂的算法：我们每次都把每个节点考虑一遍。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
#define MAXFARM	100
 
int nfarm;
int dist[MAXFARM][MAXFARM];
int isconn[MAXFARM];
 
void
main(void)
{
    FILE *fin, *fout;
    int i, j, nfarm, nnode, mindist, minnode, total;
 
    fin = fopen("agrinet.in", "r");
    fout = fopen("agrinet.out", "w");
    assert(fin != NULL && fout != NULL);
 
    fscanf(fin, "%d", &nfarm);
    for(i=0; i<nfarm; i++)
    for(j=0; j<nfarm; j++) 
	fscanf(fin, "%d", &dist[i][j]);
 
    total = 0;
    isconn[0] = 1;
    nnode = 1;
    for(isconn[0]=1, nnode=1; nnode < nfarm; nnode++) {
	mindist = 0;
	for(i=0; i<nfarm; i++)
	for(j=0; j<nfarm; j++) {
	    if(dist[i][j] && isconn[i] && !isconn[j]) {
	    	if(mindist == 0 || dist[i][j] < mindist) {
		    mindist = dist[i][j];
		    minnode = j;
		}
	    }
	}
	assert(mindist != 0);
 
	isconn[minnode] = 1;
	total += mindist;
    }
 
    fprintf(fout, "%d\n", total);
 
    exit(0);
}

—————————————————————————

[编辑] Prim算法

又是一个裸题、把基本的Prim看懂了就会做.直接套模型.首先随便将一个点加入最小生成树中，然后每次取最小的边加入，重复n-1次就可以得到一颗完整的最小生成树.数据范围也小得可以.。

直接贴代码了、给个p版的..

USER: Li Haoyu [hyli8271]
TASK: agrinet
LANG: PASCAL
 
Compiling...
Compile: OK
 
Executing...
   Test 1: TEST OK [0.000 secs, 316 KB]
   Test 2: TEST OK [0.000 secs, 316 KB]
   Test 3: TEST OK [0.000 secs, 316 KB]
   Test 4: TEST OK [0.000 secs, 316 KB]
   Test 5: TEST OK [0.000 secs, 316 KB]
   Test 6: TEST OK [0.000 secs, 316 KB]
   Test 7: TEST OK [0.000 secs, 316 KB]
   Test 8: TEST OK [0.000 secs, 316 KB]
   Test 9: TEST OK [0.000 secs, 316 KB]
   Test 10: TEST OK [0.000 secs, 316 KB]
 
All tests OK.
 
{
ID:hyli8271
PROB:agrinet
LANG:PASCAL
}
 
var
  n,sum:longint;
  gn:array[0..101,0..101]of longint;
  closedge:array[0..101]of record
                             lowcost:longint;
                             vex:longint;
                           end;
 
procedure init;
var
  i,s:integer;
begin
  readln(n);
  for i:=1 to n do
    for s:=1 to n do
      read(gn[i,s]);
end;
 
procedure Prim;
var
  i,k,j,min:longint;
begin
  for i:=1 to n do
    if i<>1 then
      closedge[i].lowcost:=gn[1,i];
  closedge[1].lowcost:=0;
  for i:=1 to n-1 do
    begin
      min:=maxlongint;
      for j:=1 to n do
        if (closedge[j].lowcost<>0)and(closedge[j].lowcost<min) then
          begin
            k:=j;
            min:=closedge[j].lowcost;
          end;
      inc(sum,min);
      closedge[k].lowcost:=0;
      for j:=1 to n do
        if gn[k,j]<closedge[j].lowcost then
          closedge[j].lowcost:=gn[k,j];
    end;
end;
 
procedure print;
begin
  writeln(sum);
end;
 
begin
  filldword(closedge,sizeof(closedge)div 4,maxlongint);
  assign(input,'agrinet.in');reset(input);
  assign(output,'agrinet.out');rewrite(output);
  init;
  Prim;
  print;
  close(input);close(output);
end.

[编辑] Alex Schwendner的分析

以上给出的方案是O(N^3)的，然而，我们可以获取O(N^2)的：我们将每个不在树中的节点到树的距离存在数组中，而不是每次都重新计算。这样，我们简单地查看每个不在树中的节点所对应的数组中的值，而不是每当添加一个节点到树中时，都检查每个在树中的点和每个不在树中的点的距离。

#include <fstream.h>
#include <assert.h>
 
const int BIG = 20000000;
 
int     n;
int     dist[1000][1000];
int     distToTree[1000];
bool    inTree[1000];
 
main ()
{
    ifstream filein ("agrinet.in");
    filein >> n;
    for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j) {
	    filein >> dist[i][j];
	}
	distToTree[i] = BIG;
	inTree[i] = false;
    }
    filein.close ();
 
    int     cost = 0;
    distToTree[0] = 0;
 
    for (int i = 0; i < n; ++i) {
	int     best = -1;
	for (int j = 0; j < n; ++j) {
	    if (!inTree[j]) {
		if (best == -1 || distToTree[best] > distToTree[j]) {
		    best = j;
		}
	    }
	}
	assert (best != -1);
	assert (!inTree[best]);
	assert (distToTree[best] < BIG);
 
	inTree[best] = true;
	cost += distToTree[best];
	distToTree[best] = 0;
	for (int j = 0; j < n; ++j) {
	    if (distToTree[j] > dist[best][j]) {
		distToTree[j] = dist[best][j];
		assert (!inTree[j]);
	    }
	}
    }
    ofstream fileout ("agrinet.out");
    fileout << cost << endl;
    fileout.close ();
    exit (0);
}