Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:求样例啊。。。。WA中,求大神帮忙看下代码

Posted by fsdcyr at 2015-01-21 20:08:51 on Problem 2784
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator