博客

A. 修路

2014新生暑假个人排位赛06

时间限制

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 代表正在修路。输入保证图是连通图。

输出格式

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

输入样例

3 2
1 2 0
1 3 1
3 2
1 2 0
1 3 0
3 2
1 2 1
1 3 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


me;



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





else


{






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:

B. 高兴

2014新生暑假个人排位赛06

时间限制

4000 ms



内存限制

65536 KB

题目描述

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

输入格式

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

输出格式

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

输入样例

2
0 1
2 0
3
0 -1 7
3 0 3
3 3 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;
}

C:

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

449. 排序

时间限制

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

D. 爱好和平

2014新生暑假个人排位赛06

时间限制

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

输出格式

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

输入样例

5 4
1 2
1 3
1 4
4 5

输出样例

1

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