概述
图论专场啊，被虐（keng）成狗了。。
A. 修路 2014新生暑假个人排位赛06
题目描述
小弱的学校很喜欢修路，现在给你一张他学校的地图，地图上有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 由于保证是连通图，所以把路修好后一定能到终点
所以，只把完好的路建一个新图，把这个新图的n个联通块之间用n-1条没修好的路连城一块就好了
所以，用并查集求联通块个数，结果减去1就好了~
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100005
using namespace std;
int n,m,sum;
int fa[maxn];
bool tongji[maxn];
int FindSet(int x)
{
if(x==fa[x]) return x;
fa[x]=FindSet(fa[x]);
return fa[x];
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int tempa,tempb,flag;
scanf("%d%d%d",&tempa,&tempb,&flag);
if(flag==0)
{
fa[FindSet(tempb)]=FindSet(tempa);
}
}
memset(tongji,false,sizeof(tongji));
sum=0;
for(int i=1;i<=n;i++)
{
if(!tongji[FindSet(i)])
{
sum++;
tongji[FindSet(i)]=true;
}
}
printf("%dn",sum-1);
}
return 0;
}-----------------------------------------------------------------------------
445. 高兴
题目描述
小弱有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 每两个玩具之间加一条边，求一条权值和最长的哈密尔顿回路，边权有负数
旅行商问题是边权非负的，求最小权值和
于是把每条边取相反数，再减去min（Hij），跑一遍旅行商
旅行商是状压dp，表示位运算太复杂写不好，比赛时用的模板，可是那个模板（poj 3311）是每个点允许经过多次，只要每个点都走过就行，所以那个tsp前面有个floyd，我直接套的模板就一直wa，比赛之后在smilewsw犇提示下发现每个玩具只能用一次，删掉了floyd就过了。。。。。。。。。。。。。。
（模板不能从其他题里扒，条件很可能不一样，一定要有自己的原始模板！
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 99999999
int mapp[19][19];
int dp[(1<<19)+100][19];
int main()
{
int i,j,n,ans,k,p;
while(~scanf("%d",&n))
{
n++;
for (i=1;i<n;i++)
{
for (j=1;j<n;j++)
{
scanf("%d",&mapp[i][j]);
mapp[i][j]=-mapp[i][j];
mapp[i][j]+=10001;
}
}
if(n==2){printf("0n");continue;}
for(i=1;i<n;i++)
{mapp[0][i]=0;mapp[i][0]=999999;mapp[i][i]=0;}
mapp[0][0]=0;
memset(dp,-1,sizeof(dp));
dp[1][0]=0;
for (i=1;i<(1<<n);i++)
{
for (j=0;j<n;j++)
{
if (dp[i][j]==-1) continue;
for (k=1;k<n;k++)
{
if ((i & (1<<k))!=0) continue;
p=(i | (1<<k));
if (dp[p][k]==-1) dp[p][k]=dp[i][j]+mapp[j][k];
dp[p][k]=min(dp[p][k],dp[i][j]+mapp[j][k]);
}
}
}
ans=INF;
for (i=1;i<n;i++)
{
if (dp[(1<<n)-1][i]>0) ans=min(ans,dp[(1<<n)-1][i]);
}
printf("%dn",(n-2)*10001-ans);
}
return 0;
}------------------------------------------------------------------------------------------------
C. 排序 2014新生暑假个人排位赛06
题目描述
给你n个数，请你将他们从小到大输出出来。
输入格式
多组数据。
输入第一行为n，接下来一行给出n个数，每个数在0到10000。
输入文件大小为8.2MB。
输出格式
输出一行，排序之后的n个数。
输入样例
3
4 2 1输出样例
1 2 4就是个桶排序嘛。。可是，这题卡分布区间的长度！！！
10000的长度，我memset了一下就超时了啊！！！
（见识了什么才叫真正的卡时间，这简直比卡常数都精确啊，原来程序里一个复杂度不是最高的过程没有优化也可以t
优化方法是，建一个used数组，把用过的点都记下来，直接输出used[i]，避免访问那些没有出现过的数
而且num数组随用随减，避免memset
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int num[10005];
int used[10005];
int temp,Id;
int n;
int main()
{
memset(num,0,sizeof(num));
while(~scanf("%d",&n))
{
Id=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&temp);
if(num[temp]==0) {Id++;used[Id]=temp;}
num[temp]++;
}
sort(used+1,used+1+Id);
for(int i=1;i<=Id-1;i++)
{
while(num[used[i] ])
{
printf("%d ",used[i]);
num[used[i] ]--;
}
}
while(num[used[Id] ]>1)
{printf("%d ",used[Id]);num[used[Id]]--;}
num[used[Id] ]--;
printf("%dn",used[Id]);
}
return 0;
}-------------------------------------------------------------------------
D. 爱好和平 2014新生暑假个人排位赛06
题目描述
在星际时代，每个帝国都靠着贸易路线连接着各个联盟星球，这些贸易路线都是双向可达的。一个帝国的综合实力由他贸易连接着的联盟星球数决定。
学姐作为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
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100005
using namespace std;
int n,m,Index,maxpos,maxsum;
int head[maxn],next[2*maxn],node[2*maxn],Dp[maxn];
bool vis[maxn];
void Addedge(int x,int y)
{
Index++;
next[Index]=head[x];
node[Index]=y;
head[x]=Index;
}
void Dfs(int src)
{
if(head[src]==0)
{
if(n-1<maxsum || (n-1==maxsum && src<maxpos)){maxsum=n-1;maxpos=src;}
Dp[src]=1;
return;
}
for(int p=head[src];p;p=next[p])
if(!vis[node[p] ])
{
vis[node[p] ]=true;
Dfs(node[p]);
}
int maxx=0;
for(int p=head[src];p;p=next[p])
{
maxx=max(maxx,Dp[node[p] ]);
Dp[src]+=Dp[node[p] ];
}
Dp[src]++;
if(max(n-Dp[src],maxx)<maxsum || (max(n-Dp[src],maxx)==maxsum && maxpos>src) )
{
maxsum=max(n-Dp[src],maxx);
maxpos=src;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
Index=0;
memset(head,0,sizeof(head));
memset(next,0,sizeof(next));
memset(vis,false,sizeof(vis));
memset(Dp,0,sizeof(Dp));
for(int i=1;i<=m;i++)
{
int tempx,tempy;
scanf("%d%d",&tempx,&tempy);
Addedge(tempx,tempy);
Addedge(tempy,tempx);
}
maxpos=maxn;
maxsum=maxn;
vis[1]=true;
Dfs(1);
printf("%dn",maxpos);
}
return 0;
}---------------------------------------------------------------------------
450. 萌学妹的手机
题目描述
学妹的手机马上就要没电了！
手机网络是由蜂窝基站提供的，手机会自动搜寻最近的一个基站连接信号。每个基站的范围为一个正六边形。作为北邮的萌妹子当然知道切换基站是很费电的，所以要尽量不切换基站。学妹有一张地图在手中，想让你帮忙规划一下线路，让自己的手机尽可能少的切换基站。
学妹的出发地和目的地均为平面直角坐标系上的点，为了方便计算，我们假设在坐标原点处有一个基站，基站范围的正六边形以基站为几何中心。
六边形的边长为L，我们假设整个平面都有信号。小学妹很聪明，所以不会在基站间的边缘行走，也不会在三个基站区域相交的顶点停留，因为这样都会让手机付出非常大的耗电代价。
学妹希望知道她最少需要穿越多少次边界才能够到达目的地。(六边形的方向为有两条边平行于y轴，有两个顶点分别朝北朝南)
输入格式
第一行为数据组数，整数T （T<=1000)
每组数据格式如下：
第一行 ： 基站范围的正六边形边长，正实数 L ( 0.1 <= L <= 10.0 )
第二行 ： 出发点坐标，两个实数Sx Sy (-150000.0 <= Sx, Sy <= 150000.0)
第三行 ： 目标点坐标，两个实数Dx Dy (-150000.0 <= Dx, Dy <= 150000.0)
输出格式
每组数据输出一行，为一个整数，表示小胖最少需要穿越的基站范围边缘的次数。
数据保证起始点终点不会在六边形边缘上。
输入样例
2
2.0
0 0
6 -1
2.0
0 0
9 -1
输出样例
2
3 这题是个叫做蜂窝网络的题改来的
我的思路是（直角坐标做的）先找出起点终点在哪个六边形中，再求两个六边形中心的最短距离
如果相对位置同时在y=根三x和y=-根三x的上方或下方，则最短路上每次走y都有变化，直接用差的绝对值除以每步y的变化量
如果在左或右，就沿y=根三x或y=-根三x走到y坐标相等，再平行x轴蹭过去，这样最短
哎呀哎呀不好描述啊啊，就详见代码吧
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define eps 0.0001
using namespace std;
int t;
double l,sx,sy,dx,dy;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf%lf%lf",&l,&sx,&sy,&dx,&dy);
l=sqrt(3)*l/2;
double canzhaox,canzhaoy,beginx,beginy,endx,endy;
if(sx>0)//qi dian
canzhaox=((int)( sx/(2*l)+eps ))*2*l;
else canzhaox=((int)( sx/(2*l)-eps )-1)*2*l;
if(sy>0)
canzhaoy=((int)( sy/(2*sqrt(3)*l)+eps ))*2*sqrt(3)*l;
else canzhaoy=((int)( sy/(2*sqrt(3)*l)-eps )-1)*2*sqrt(3)*l;
//printf("%.3lf %.3lfn",canzhaox,canzhaoy);
if(sx<canzhaox+l)
{
if(sy-canzhaoy-2*sqrt(3)/3*l+sqrt(3)/3*(sx-canzhaox) <0 ) {beginx=canzhaox;beginy=canzhaoy;}
else
{
if(sy-canzhaoy-4*sqrt(3)/3*l-sqrt(3)/3*(sx-canzhaox) >0 ) {beginx=canzhaox;beginy=canzhaoy+2*sqrt(3)*l;}
else {beginx=canzhaox+l;beginy=canzhaoy+sqrt(3)*l;}
}
}
else
{
if(sy-canzhaoy-2*sqrt(3)/3*l-sqrt(3)/3*(sx-canzhaox-2*l) <0 ) {beginx=canzhaox+2*l;beginy=canzhaoy;}
else
{
if(sy-canzhaoy-4*sqrt(3)/3*l+sqrt(3)/3*(sx-canzhaox-2*l) >0 ) {beginx=canzhaox+2*l;beginy=canzhaoy+2*sqrt(3)*l;}
else {beginx=canzhaox+l;beginy=canzhaoy+sqrt(3)*l;}
}
}
// printf("%.3lf %.3lfn",beginx,beginy);
if(dx>0)//zhong dian
canzhaox=((int)( dx/(2*l)+eps ))*2*l;
else canzhaox=((int)( dx/(2*l)-eps )-1)*2*l;
if(dy>0)
canzhaoy=((int)( dy/(2*sqrt(3)*l)+eps ))*2*sqrt(3)*l;
else canzhaoy=((int)( dy/(2*sqrt(3)*l)-eps )-1)*2*sqrt(3)*l;
//printf("%.3lf %.3lfn",canzhaox,canzhaoy);
if(dx<canzhaox+l)
{
if(dy-canzhaoy-2*sqrt(3)/3*l+sqrt(3)/3*(dx-canzhaox) <0 ) {endx=canzhaox;endy=canzhaoy;}
else
{
if(dy-canzhaoy-4*sqrt(3)/3*l-sqrt(3)/3*(dx-canzhaox) >0 ) {endx=canzhaox;endy=canzhaoy+2*sqrt(3)*l;}
else {endx=canzhaox+l;endy=canzhaoy+sqrt(3)*l;}
}
}
else
{
if(dy-canzhaoy-2*sqrt(3)/3*l-sqrt(3)/3*(dx-canzhaox-2*l) <0 ) {endx=canzhaox+2*l;endy=canzhaoy;}
else
{
if(dy-canzhaoy-4*sqrt(3)/3*l+sqrt(3)/3*(dx-canzhaox-2*l) >0 ) {endx=canzhaox+2*l;endy=canzhaoy+2*sqrt(3)*l;}
else {endx=canzhaox+l;endy=canzhaoy+sqrt(3)*l;}
}
}
if( ((endy-beginy)-sqrt(3)*(endx-beginx))*((endy-beginy)+sqrt(3)*(endx-beginx)) >0 )
printf("%dn",(int)(abs(endy-beginy)/(sqrt(3)*l) +eps) );
else
{
int ansy=(int)(abs(endy-beginy)/(sqrt(3)*l) +eps);
int ansx=(int)( (abs(endx-beginx)-ansy*l)/2/l+eps );
printf("%dn",ansy + ansx);
}
}
return 0;
}===================================EOF=======================================
最后
以上就是勤劳毛衣为你收集整理的Asce's Summer Ranking No.6 A. 修路 2014新生暑假个人排位赛06 445. 高兴 C. 排序 2014新生暑假个人排位赛06 D. 爱好和平 2014新生暑假个人排位赛06 450. 萌学妹的手机的全部内容，希望文章能够帮你解决Asce's Summer Ranking No.6 A. 修路 2014新生暑假个人排位赛06 445. 高兴 C. 排序 2014新生暑假个人排位赛06 D. 爱好和平 2014新生暑假个人排位赛06 450. 萌学妹的手机所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复