P1119 灾后重建

题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出 B 地区的村庄数 N，村庄编号从 0 到 N−1，和所有 M 条公路的长度，公路是双向的。并给出第 i 个村庄重建完成的时间 ti​，你可以认为是同时开始重建并在第 ti​ 天重建完成，并且在当天即可通车。若 ti​ 为 0 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 Q 个询问 (x,y,t)，对于每个询问你要回答在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要输出 −1。

输入格式

第一行包含两个正整数 N,M，表示了村庄的数目与公路的数量。

第二行包含 N 个非负整数 t0​,t1​,⋯,tN−1​，表示了每个村庄重建完成的时间，数据保证了 t0​≤t1​≤⋯≤tN−1​。

接下来 M 行，每行 3 个非负整数 i,j,w，w 不超过 10000，表示了有一条连接村庄 i 与村庄 j 的道路，长度为 w，保证 i=j，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 M+3 行包含一个正整数 Q，表示 Q 个询问。

接下来 Q 行，每行 3 个非负整数 x,y,t，询问在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少，数据保证了 t 是不下降的。

输出格式

共 Q 行，对每一个询问 (x,y,t) 输出对应的答案，即在第 t 天，从村庄 x 到村庄 y 的最短路径长度为多少。如果在第 t 天无法找到从 x 村庄到 y 村庄的路径，经过若干个已重建完成的村庄，或者村庄 x 或村庄 y 在第 t 天仍未修复完成，则输出 −1。

输入输出样例

输入 #1复制

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

输出 #1复制

-1
-1
5
4

说明/提示

对于 30% 的数据，有 N≤50；

对于 30% 的数据，有 ti​=0，其中有 20% 的数据有 ti​=0 且 N>50；

对于 50% 的数据，有 Q≤100；

对于 100% 的数据，有 1≤N≤200，0≤M≤2N×(N−1)​，1≤Q≤50000，所有输入数据涉及整数均不超过 105。

实现代码：

#include<iostream>
#include<cstdio>
#define N 205
using namespace std;
int n,m;
int a[N];
int f[N][N];
inline void updata(int k){
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	if(f[i][j]>f[i][k]+f[j][k])
	f[i][j]=f[j][i]=f[i][k]+f[j][k];
	return;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
	scanf("%d",a+i);
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++){
		f[i][j]=1e9;
	}
	for(int i=0;i<n;i++)
	f[i][i]=0;
	int s1,s2,s3;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&s1,&s2,&s3);
		f[s1][s2]=f[s2][s1]=s3;
	}
	int q;
	cin>>q;
	int now=0;
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&s1,&s2,&s3);
		while(a[now]<=s3&&now<n){
			updata(now);
			now++;
		}
		if(a[s1]>s3||a[s2]>s3)cout<<-1<<endl;
		else {
			if(f[s1][s2]==1e9)cout<<-1<<endl;
			else cout<<f[s1][s2]<<endl;
		}
	}
	return 0;
} 

P1037 [NOIP 2002 普及组] 产生数

题目描述

给出一个整数 n 和 k 个变换规则。

规则：

• 一位数可变换成另一个一位数。
• 规则的右部不能为零。

例如：n=234,k=2。有以下两个规则：

• 2⟶5。
• 3⟶6。

上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

• 234。
• 534。
• 264。
• 564。

共 4 种不同的产生数。

现在给出一个整数 n 和 k 个规则。求出经过任意次的变换（0 次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入格式

第一行两个整数 n,k，含义如题面所示。

接下来 k 行，每行两个整数 xi​,yi​，表示每条规则。

输出格式

共一行，输出能生成的数字个数。

输入输出样例

输入 #1复制

234 2
2 5
3 6

输出 #1复制

4

说明/提示

对于 100% 数据，满足 n<1030，k≤15。

【题目来源】

NOIP 2002 普及组第三题

 实现代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char ans[40],s[40];int K,check[10],dis[10][10],t[10];

void times(int tmp)
{
	int l=strlen(ans),x=0,cnt=0;
	if(tmp==10)
	{
		for(int i=l;i>0;i--) ans[i]=ans[i-1];
		ans[0]='0';
    }
    else
	{
		for(int i=0;i<l;i++)
		{
			x=(ans[i]-'0')*tmp+cnt;
			cnt=x;
			if(x>=10)
			{
				x%=10;	
			}
			ans[i]=x+'0';
			cnt=(cnt-x)/10;
		}
		if(cnt) ans[l]=cnt+'0';
	}
}
int main()
{
	scanf("%s %d",s,&K);
	int L=strlen(s);
	for(int i=0;i<L;i++) 
	    check[s[i]-'0']++;
	ans[0]='1';
	memset(dis,0,sizeof(dis));
	
	for(int i=1;i<=K;i++)
	{
		int a,b;
		cin>>a>>b;
		dis[a][b]=1;
	} 
	
	for(int k=0;k<=9;k++)
	{
		for(int i=0;i<=9;i++)
		{
			for(int j=0;j<=9;j++)
			{
				if(dis[i][j] || (dis[i][k]&&dis[k][j])) dis[i][j]=1;
			}
		}
	}
	for(int i=0;i<=9;i++)
		dis[i][i]=0; 
	for(int i=0;i<=9;i++) 
	{
		int tmp=1;
		for(int j=0;j<=9;j++)
		{
			if(dis[i][j] && check[i]) tmp++;
		}
		if(s[0]-'0'==i && dis[i][0]) tmp--;
		t[i]=tmp;
	}
	for(int i=0;i<L;i++) if(t[s[i]-'0']) times(t[s[i]-'0']);
	
	int L_=strlen(ans);
	for(int i=L_-1;i>=0;i--) cout<<ans[i];
	return 0;
}

P2419 [USACO08JAN] Cow Contest S

题目描述

FJ 的 N（1≤N≤100）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 1,2,⋯,N 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 A 的奶牛的编程能力强于编号为 B 的奶牛（1≤A,B≤N，A=B)，那么她们的对决中，编号为 A 的奶牛总是能胜出。FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M（1≤M≤4,500）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

输入格式

第一行两个用空格隔开的整数 N,M。

第 2∼M+1 行，每行为两个用空格隔开的整数 A,B ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为胜者）。

输出格式

输出一行一个整数，表示排名可以确定的奶牛的数目。

输入输出样例

输入 #1复制

5 5
4 3
4 2
3 2
1 2
2 5

输出 #1复制

2

说明/提示

样例解释：

编号为 2 的奶牛输给了编号为 1,3,4 的奶牛，也就是说她的水平比这 3 头奶牛都差。而编号为 5 的奶牛又输在了她的手下，也就是说，她的水平比编号为 5 的奶牛强一些。于是，编号为 2 的奶牛的排名必然为第 4，编号为 5 的奶牛的水平必然最差。其他 3 头奶牛的排名仍无法确定。

 实现代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a,b,n,m,f[101][101],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        f[a][b]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
              f[i][j]=f[i][j]|f[i][k]&f[k][j];
    for(int i=1;i<=n;i++){
        int gg=1;
        for(int j=1;j<=n;j++)
        if(i==j)continue;else 
         gg=gg&(f[i][j]|f[j][i]);
         ans+=gg;
    }
    printf("%d\n",ans);
}

P2047 [NOI2007] 社交网络

题目描述

在社交网络（Social Network）的研究中，我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题：
在一个社交圈子里有 n 个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个 n 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 c，c 越小，表示两个人之间的关系越密切。我们可以用对应结点之间的最短路长度来衡量两个人 s 和 t 之间的关系密切程度，注意到最短路径上的其他结点为 s 和 t 的联系提供了某种便利，即这些结点对于 s 和 t 之间的联系有一定的重要程度。我们可以通过统计经过一个结点 v 的最短路径的数目来衡量该结点在社交网络中的重要程度。考虑到两个结点 A 和 B 之间可能会有多条最短路径。我们修改重要程度的定义如下：令 Cs,t​ 表示从 s 到 t 的不同的最短路的数目，Cs,t​(v) 表示经过 v 从 s 到 t 的最短路的数目；则定义：

I(v)=s=v,t=v∑​Cs,t​Cs,t​(v)​

为结点 v 在社交网络中的重要程度。为了使 I(v) 和 Cs,t​(v) 有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。

输入格式

输入第一行有两个整数 n 和 m，表示社交网络中结点和无向边的数目。
在无向图中，我们将所有结点从 1 到 n 进行编号。

接下来 m 行，每行用三个整数 a,b,c 描述一条连接结点 a 和 b，权值为 c 的无向边。 注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

输出格式

输出包括 n 行，每行一个实数，精确到小数点后 3 位。第 i 行的实数表示结点 i 在社交网络中的重要程度。

输入输出样例

输入 #1复制

4 4
1 2 1
2 3 1
3 4 1
4 1 1

输出 #1复制

1.000
1.000
1.000
1.000

说明/提示

对于 1 号结点而言，只有 2 号到 4 号结点和 4 号到 2 号结点的最短路经过 1 号结点，而 2号结点和 4 号结点之间的最短路又有 2 条。因而根据定义， 1 号结点的重要程度计算为 21​+21​=1。由于图的对称性，其他三个结点的重要程度也都是 1。

对于 50% 的数据，n≤10,m≤45。
对于 100% 的数据，n≤100,m≤4500，任意一条边的权值 c 是正整数且 1⩽c⩽1000。
所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 1010。

 实现代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=110,maxm=4510;
int n,m,cnt,last[maxn];
long long dis[maxn][maxn];
long long ce[maxn][maxn];
double value[maxn];
inline void add(int u,int v,int w){
    dis[u][v]=w;
    ce[u][v]++; 
}
int main(){
    cin>>n>>m;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        add(u,v,w),add(v,u,w);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    ce[i][j]=ce[i][k]*ce[k][j];
                }
                else if(dis[i][j]==dis[i][k]+dis[k][j]){
                    ce[i][j]+=ce[i][k]*ce[k][j];
                }
            }
        }
    }
    for(int v=1;v<=n;v++){//计算v的value 
        for(int s=1;s<=n;s++){
            if(s==v) continue;
            for(int t=1;t<=n;t++){
                if(t==v || s==t) continue;
                if(dis[s][v]+dis[v][t]==dis[s][t]){
                    long long tmp=ce[s][v]*ce[v][t];
                    value[v]+=1.0*tmp/ce[s][t];
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%.3lf\n",value[i]);
    }
    return 0;
}