北邮新生排位赛6解题报告

时间限制

3000 ms

内存限制

65536 KB

题目描述

小弱的学校很喜欢修路，现在给你一张他学校的地图，地图上有n个点和m条双向边，每条边代表一条路，这条路有可能是畅通，也有可能正在修路。大家都知道修路使得交通很不方便。所有小弱很想学校快快的把路修好，使得他能够很轻松的到达主楼915去刷题。但考虑到学校的施工能力有限，小弱想让你帮他算出学校需要集中力量马上修好的最少路数，使得他能够从学校任意点出发，在不经过正在施工的路下到达主楼（编号为1）。

输入格式

有多组数据。

每组数据以n( 1<=n<=10000), m(1<=m<=200000)开头。接下来一行有m行数。每行有三个数，对应于u, v, s,分别为这条路的两端点(编号从1到n)和路况，s = 0代表畅通, s = 1 代表正在修路。输入保证图是连通图。

输出格式

对每组数据输出对应的最少路数。

输入样例

输出样例

1
0
2

简单的并查集而已...各种姿势出错

       
        #include <cstdio>

       
        using

        namespace

        std;

       
        const

        int

        MAXN=10001;

       
        const

        int

        MAXM=400004;

       
        int

        par[MAXN];

       
        struct

        edge{

       
        int

        from,to;

};

       
        edge e[MAXM];

       
        int

        n,m;

       
        int

        fpar(

        int

        i){

        if

        (par[i]==i)

        return

        i;

        else

        return

        par[i]=fpar(par[i]);}

       
        bool

        same(

        int

        a,

        int

        b){

        return

        (fpar(a)==fpar(b));}

       
        void

        unit(

        int

        a,

        int

        b){

        if

        (!same(a,b))par[fpar(a)]=fpar(b);}

       
        int

        kruskal(){

       
        int

        ret=0;

       
        for

        (

        int

        i=0;i<me;i++){

       
        if

        (!same(e[i].from,e[i].to)){

       
        unit(e[i].from,e[i].to);

       
        ret++;

}

}

       
        return

        ret;

}

       
        int

        solve(){

       
        int

        tf,tt,tc;

       
        for

        (

        int

        i=1;i<=n;i++){par[i]=i;}

       
        me=0;

       
        for

        (

        int

        i=0;i<m;i++){

       
        scanf

        (

        "%d%d%d"

        ,&tf,&tt,&tc);

       
        if

        (tc==0)unit(tf,tt);

       
        if

        (!same(tf,tt)){

       
        e[me].from=tf;e[me].to=tt;me++;

       
        e[me].from=tt;e[me].to=tf;me++;

}

}

}

       
        int

        ans=kruskal();

       
        printf

        (

        "%d\n"

        ,ans);

       
        return

        0;

}

       
        int

        main(){

       
        while

        (

        scanf

        (

        "%d%d"

        ,&n,&m)==2){

       
        solve();

}

       
        return

        0;

}

B:

时间限制

4000 ms

内存限制

65536 KB

题目描述

小弱有n个玩具，现在小弱想把他们排列成一行，把玩具j放在玩具i的右边相邻的位置上，他将得到一个高兴值Hij.

输入格式

输入有多组数据。每组数据以一个整数n(n <= 18)开头。接下来n行，每行n个整数。第i行第j列Hij( Hij的绝对值 <= 10000)代表把玩具j放在玩具i的右边相邻的位置时高兴值。输入保证Hii = 0,最左边只考虑与右边相邻的玩具，最右边只考虑与左边相邻的玩具。

输出格式

对于每组数据输出最大高兴值。

输入样例

输出样例

2 
10

…….旅行商就旅行商呗….居然还真卡在n^n^2^n

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXM=1<<18;
const int MINDP=-200000;
int dp[MAXM][18];
bool vis[MAXM][18];
int h[18][18];

int n;
int dfs(int last,int m){
//printf("dfs(%d,%d)begin\n",last,m);
    if(vis[m|(1<<last)][last]){
//printf("dp[%d][%d]%d\n",(m|(1<<last)),last,dp[m|(1<<last)][last]);
            return dp[m|(1<<last)][last];
    }
    if(m==0){
        vis[1<<last][last]=true;
        dp[1<<last][last]=0;
        return 0;
    }
    dp[m|(1<<last)][last]=MINDP;
    for(int i=0;i<n;i++){
        if(m&(1<<i))dp[m|(1<<last)][last]=max( dp[m|(1<<last)][last],(dfs(i,(m^(1<<i)))+h[i][last]));
    }
    vis[m|(1<<last)][last]=true;
//printf("dp[%d][%d]%d\n",(m|(1<<last)),last,dp[m|(1<<last)][last]);
    return dp[m|(1<<last)][last];
}
int main(){
    while(scanf("%d",&n)==1){
        for(int i=1;i<=((1<<n)-1);i++)memset(vis[i],0,sizeof(vis[i]));
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&h[i][j]);
            }
        }
        int maxn=(1<<n)-1;
//printf("maxn%d\n",maxn);
        for(int i=0;i<n;i++)dfs(i,(maxn^(1<<i)));
        int maxans=MINDP;
        for(int i=0;i<n;i++)maxans=max(maxans,dp[(1<<n)-1][i]);
        printf("%d\n",maxans);
    }
    return 0;
}

坑爹的排序....不过受周围"别人都没做出来"影响太重

时间限制

1000 ms

内存限制

65536 KB

题目描述

给你n个数，请你将他们从小到大输出出来。

输入格式

多组数据。

输入第一行为n，接下来一行给出n个数，每个数在0到10000。

输入文件大小为8.2MB。

输出格式

输出一行，排序之后的n个数。

输入样例

3
4 2 1

输出样例

1 2 4

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXM=10001;
int n;
int num[MAXM];
int heap[MAXM];
int main(){
        while(scanf("%d",&n)==1){
            if(n==0)continue;
            int pheap=0;
            for(int i=0;i<n;i++){
                int temp;
                scanf("%d",&temp);
                if(num[temp]==0){
                    heap[pheap++]=temp;
                }
                num[temp]++;
            }
            if(pheap<=1000){
                sort(heap,heap+pheap);
                for(int i=0;i<pheap;i++){
                    while(num[heap[i]]){
                        printf("%d",heap[i]);
                        n--;num[heap[i]]--;
                        if(n)printf(" ");
                        else printf("\n");
                    }
                }
                continue;
            }
            for(int i=0;i<10001;i++){
                while(num[i]){
                    printf("%d",i);
                    n--;num[i]--;
                    if(n)printf(" ");
                    else printf("\n");
                }
            }
        }
        return 0;
}

时间限制

1000 ms

内存限制

65536 KB

题目描述

在星际时代，每个帝国都靠着贸易路线连接着各个联盟星球，这些贸易路线都是双向可达的。一个帝国的综合实力由他贸易连接着的联盟星球数决定。学姐作为Mays帝国的领袖，长期与Luke帝国保持着敌对关系，爱好和平的学姐希望结束长达几个世纪的战争，于是找实验室定做了一颗代号小苹果的炸弹，可以定点摧毁一颗星球，这颗星球被毁后，与它相连的全部贸易就都被切断了，这样Luke帝国可能就被切断为一个小联盟，他们就再也不会对学姐的地位构成威胁啦～经过调查，Luke帝国为了节约经费，他的联盟星之间都有且仅有一条直接或间接的贸易通路。现在给出Luke帝国的贸易线路，学姐想知道摧毁哪一颗行星可以使得分裂后的若干Luke联盟威胁最大的分部最小。

输入格式

输入有多组数据，组数不大于10组。每一组开头一行为n，m，表示Luke帝国的联盟星球数量，和贸易关系数，接下来m行，每行两个整数u，v，表示星球u,v之间存在直接的贸易路线，1<=u,v<=n，1<=n,m<=100000

输出格式

输出一个数表示推荐学姐摧毁的星球，如果有多解，输出编号最小的一个。

输入样例

输出样例

1 建立单向边的时候会覆盖丢失数据新姿势: 通过vis数组,因为只有”直接或间接的一条路径”,所以更新时除去vis[true]的节点(父节点)即可,不过因为重新计算最大子树大小时,vis已经全部被改所以增加 pre 2 变量未初始化编译器不提醒…

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int MAXM= 100001;
 
int dp[MAXM];
int first[MAXM];
int to[2*MAXM];
int pre[MAXM];
int next[2*MAXM];
bool vis[MAXM];
int maxpoint,maxans;
int dfs(int s){
    if(vis[s])return dp[s];
    vis[s]=true;
    dp[s]=0;
    for(int p=first[s];p!=-1;p=next[p]){
        if(vis[to[p]])continue;
        int tempd=dfs(to[p]);
        pre[to[p]]=s;
        dp[s]+=tempd;
    }
    return ++dp[s];
}
void addedge(int tfrom,int tto,int index){
        to[index]=tto;
        next[index]=first[tfrom];
        first[tfrom]=index;
}
int main(){
    for(int ti=1;scanf("%d%d",&n,&m)==2;ti++){
        memset(first,-1,sizeof(first));
        memset(vis,0,sizeof(vis));
        for(int i=0;i<m;i++){
            int tfrom,tto;
            scanf("%d%d",&tfrom,&tto);
            addedge(tfrom,tto,2*i);addedge(tto,tfrom,2*i+1);
        }
        maxans=0;
        maxpoint=0x7fffffff;
        dfs(1);
        for(int i=1;i<=n;i++){
            int maxson=n-dp[i];
            for(int p=first[i];p!=-1;p=next[p]){
                if(pre[i]!=to[p])maxson=max(maxson,dp[to[p]]);
            }
            if(maxson<maxpoint){
                maxpoint=maxson;maxans=i;
            }
        }
        printf("%d\n",maxans);
    }
    return 0;
}

转载于:https://www.cnblogs.com/xuesu/p/4041486.html