Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:求样例啊。。。。WA中,求大神帮忙看下代码In Reply To:求样例啊。。。。WA中 Posted by:fsdcyr at 2015-01-21 19:46:59 > 样例过了。 > 这题有什么细节吗 #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i,a,b) for(int i=(a);i<=(b);++i) #define mes(s,c) memset(s,c,sizeof(s)) const int maxn=1010; #define INF 0x3f3f3f3f using namespace std; int MST_w; int n,m; int f[maxn]; struct Edge{ int u,v; int w; Edge(int from,int to,int d):u(from),v(to),w(d){} bool operator<(const Edge&x)const{ return w<x.w; } }; vector<Edge> edges; struct val{ int node[maxn]; int cnt; int w; }c[10]; vector<pair<int,int> >node; void makeSet(){REP(i,n+1)f[i]=i;} int find(int x) { return f[x]==x?x:f[x]=find(f[x]); } int MST[maxn]; void kruskal() { sort(edges.begin(),edges.end()); makeSet();int cnt=0; MST_w=0; REP(i,edges.size()){ int f_u=find(edges[i].u); int f_v=find(edges[i].v); if(f_u!=f_v){ f[f_u]=f_v; MST[cnt++]=i; MST_w+=edges[i].w; if(cnt==n-1) break; } } // cout<<"最小生成树=="<<MST_w<<endl; } void _kruskal(int &w) { REP(i,n-1){ int f_u=find(edges[MST[i]].u); int f_v=find(edges[MST[i]].v); if(f_u!=f_v){ w+=edges[MST[i]].w; f[f_u]=f_v; } } } void solve() { int ans=MST_w; REP(i,1<<m){ makeSet(); int w=0; REP(j,m){ if(i&(1<<j)){//枚举子集 w+=c[j].w; REP(k,c[j].cnt-1){//将套餐中的点连通 int f_u=c[j].node[k]; int f_v=c[j].node[k+1]; if(f_u!=f_v) f[f_u]=f_v; } } }//最小生成树 _kruskal(w); ans=min(ans,w); } printf("%d\n",ans); } int main() { #ifndef ONLINE_JUDGE freopen("in.cpp","r",stdin); #endif // ONLINE_JUDGE scanf("%d%d",&n,&m); node.clear();edges.clear(); REP(i,m){scanf("%d%d",&c[i].cnt,&c[i].w);REP(j,c[i].cnt)scanf("%d",&c[i].node[j]);}//输入套餐 REP(i,n){//输入点坐标 int x,y; scanf("%d%d",&x,&y); node.push_back(make_pair(x,y)); } REP(i,n)FOR(j,i+1,n){//预处理边权 int x=int(node[i].first-node[j].first); int y=int(node[i].second-node[j].second); int w=x*x+y*y; edges.push_back(Edge(i+1,j+1,w)); } kruskal();//求原图的MST,记录边的序号 solve(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator