POJ - 1258 Agri-Net （最小生成树）

#include<iostream>#include<cmath>#include<cstring>#include<queue>#include<vector>#include<cstdio>#include<algorithm>#include<map>#include<set>#define rep(i,e) for(int i=0;i<(e);i++)#define rep1(i,e) for(int i=1;i<=(e);i++)#define repx(i,x,e) for(int i=(x);i<=(e);i++)#define X first#define Y second#define PB push_back#define MP make_pair#define mset(var,val) memset(var,val,sizeof(var))#define scd(a) scanf("%d",&a)#define scdd(a,b) scanf("%d%d",&a,&b)#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)#define pd(a) printf("%d\n",a)#define scl(a) scanf("%lld",&a)#define scll(a,b) scanf("%lld%lld",&a,&b)#define sclll(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;typedef long long ll;template <class T>void test(T a){cout<<a<<endl;}template <class T,class T2>void test(T a,T2 b){cout<<a<<" "<<b<<endl;}template <class T,class T2,class T3>void test(T a,T2 b,T3 c){cout<<a<<" "<<b<<" "<<c<<endl;}template <class T>inline bool scan_d(T &ret){ ???char c;int sgn; ???if(c=getchar(),c==EOF) return 0; ???while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar(); ???sgn=(c==‘-‘)?-1:1; ???ret=(c==‘-‘)?0:(c-‘0‘); ???while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret = ret*10+(c-‘0‘); ???ret*=sgn; ???return 1;}//const int N = 1e6+10;const int inf = 0x3f3f3f3f;const ll INF = 0x3f3f3f3f3f3f3f3fll;const ll mod = 1000000000;int T;void testcase(){ ???printf("Case %d:",++T);}const int MAXN = 2500 ;const int MAXM = 550;const double eps = 1e-8;const double PI = acos(-1.0);bool vis[MAXN];int lowc[MAXN];int cost[MAXN][MAXN];int Prim(int n){ ???int ans=0; ???mset(vis,false); ???vis[0]=true; ???for(int i=1;i<n;i++) lowc[i]=cost[0][i]; ???for(int i=1;i<n;i++){ ???????int minc = inf; ???????int p = -1; ???????for(int j=0;j<n;j++){ ???????????if(!vis[j]&&minc>lowc[j]){ ???????????????minc = lowc[j]; ???????????????p = j; ???????????} ???????} ???????if(minc == inf){ ???????????return -1; ???????} ???????ans+=minc; ???????vis[p]=true; ???????for(int j=0;j<n;j++){ ???????????if(!vis[j]&&lowc[j]>cost[p][j]){ ???????????????lowc[j] = cost[p][j]; ???????????} ???????} ???} ???return ans;}int main() {#ifdef LOCAL ???freopen("data.in","r",stdin);#endif // LOCAL ???int n; ???while(~scanf("%d",&n)){ ???????for(int i=0;i<n;i++){ ???????????for(int j=0;j<n;j++){ ???????????????scanf("%d",&cost[i][j]); ???????????} ???????} ???????int ans=Prim(n); ???????printf("%d\n",ans); ???} ???return 0;}