POJ 3357 Oreon
制約条件
頂点数≦26
ソースコード
struct edge{ int u, v, cost; bool operator<(const edge &r)const{ if(cost!=r.cost)return cost<r.cost; return min(u,v)!=min(r.u,r.v)?min(u,v)<min(r.u,r.v):max(u,v)<max(r.u,r.v); } }; int n; int p[30]; int root(int x){ if(x==p[x])return x; return p[x]=root(p[x]); } int main() { int CS; scanf("%d",&CS); rep(cs,CS){ scanf("%d",&n); vector<edge> es; rep(i,n)rep(j,n){ int d; scanf("%d,",&d); if(d)es.push_back((edge){ i, j, d } ); } sort(all(es)); rep(i,n)p[i]=i; printf("Case %d:\n",cs+1); int i=0; while(n>1&&i<es.size()){ int u=es[i].u, v=es[i].v, c=es[i].cost; int a=root(u), b=root(v); i++; if(a==b)continue; p[a]=b; printf("%c-%c %d\n",min(u,v)+'A',max(u,v)+'A',c); n--; i++; } } return 0; }