| ||||||||||
| 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