Home > Old Blog Posts > USACO 3.1.1 Agri-Net

USACO 3.1.1 Agri-Net


一道标准的最小生成树,裸的模型,选择自己喜欢的算法来编吧。

代码:

/*
ID: dementr1
PROG: agrinet
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“agrinet.in”);
ofstream fout(“agrinet.out”);
int N,length=0,a[100][100]={};
void init()
{
int i,j;
fin>>N;
for(i=0;i<N;i++)
for(j=0;j<N;j++) fin>>a[i][j];
fin.close();
}
void work()
{
int time,num,i,j,min,minj;
bool used[100]={false};
used[0]=true;
num=0;
for(time=1;time<N;time++)
{
min=99999999;
for(i=0;i<N;i++)
if(used[i])
{
for(j=0;j<N;j++)
if(i!=j&&!used[j]&&a[i][j]<min)
{
min=a[i][j];
minj=j;
}
}
used[minj]=true;
length+=min;
}
fout<<length<<endl;
fout.close();
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: