织梦装修设计网站模板,网站如何上传数据库,wordpress网页设计价格设计,更合高明网站建设Tyvj 2059 元芳看电影 描述 神探狄仁杰电影版首映这天#xff0c;狄仁杰、李元芳和狄如燕去看电影。由于人实在是太多了#xff0c;入场的队伍变得十分不整齐#xff0c;一个人的前面可能会出现并排的好多人。“元芳#xff0c;这队伍你怎么看#xff1f;”“大人#xf… Tyvj 2059 元芳看电影 描述 神探狄仁杰电影版首映这天狄仁杰、李元芳和狄如燕去看电影。由于人实在是太多了入场的队伍变得十分不整齐一个人的前面可能会出现并排的好多人。“元芳这队伍你怎么看”“大人卑职看不出这队伍是怎么排的但是卑职看出了一些两个人之间的前后关系”“那么我们可以写个程序计算出来一定没有和其它人并排的人数。”“大人/叔父真乃神人也” 输入格式 第一行两个数N、M表示队伍一共有N个人元芳看出了M对关系。接下来M行每行两个数a、b表示a在b的前面不一定正好在b的前面ab之间可能有其他人。 输出格式 有多少个人一定没有和其他人并排。 测试样例1 输入 3 21 21 3 输出 1 备注 对于100%的数据1N1000M4500。数据保证M对关系不出现矛盾。sjynoi 思路floyd传递闭包如果所有人除了自己都在都在自己的前或后就一定不并排 1 #includeiostream2 #includecstdio3 #includestring4 #includecstring5 #includealgorithm6 #includevector7 using namespace std;8 const int maxn 105;9 const int maxint 100000000;
10 int n,m,g[maxn][maxn],tg[maxn][maxn],ans,nowans;
11 void input(){
12 cinnm;
13 int u,v;
14 for(int i 1;i m;i){
15 cinuv;
16 g[u][v] 1;
17 }
18 }
19 void build(){
20 for(int k 1;k n;k){
21 for(int i 1;i n;i){
22 for(int j 1;j n;j){
23 if(k ! i k ! j i ! j) g[i][j] g[i][j] || (g[i][k] g[k][j]);
24 }
25 }
26 }
27 for(int i 1;i n;i){
28 nowans 0;
29 for(int j 1;j n;j){
30 if(g[i][j]) nowans;
31 if(g[j][i]) nowans;
32 }
33 if(nowans n-1) ans;
34 }
35 coutansendl;
36 }
37 int main(){
38 input();
39 build();
40 } View Code Tyvj 1139 向远方奔跑APIO 2009 抢掠计划 描述 在唐山一中吃饭是一件很令人头疼的事情因为你不可能每次都站在队伍前面买饭所以你最需要做的一件事就是——跑饭。而跑饭的道路是无比艰难的因为路是单向的你要非说成是双向的我也没法前提是你可以逆着2000个狂热的跑饭群众而行所以要合理选择路线。并且在抵达你的目的地——板面馆之前你需要先买一些干粮比如烧饼之类的。现在给你每个干食商店的位置和干食喜爱度请你设计一个跑饭方案使得在到达板面馆之前能得到尽可能多的干食喜爱度。 输入格式 第一行包含两个整数N、M。N表示食品商店的个数M表示道路条数。接下来M行每行两个整数这两个整数都在1到N之间第i1行的两个整数表示第i条道 路的起点和终点的食品商店编号。接下来N行每行一个整数按顺序表示每个食品商店处的干食喜爱度。接下来一行包含两个整数S、PS表示学校的编号也就是出发地点。P表示板面馆数目。接下来的一行中有P个整数表示P个卖板面的食品商店的编号。 输出格式 输出一个整数表示到达板面馆之前能得到的最多的干食喜爱度。 测试样例1 输入 6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6 输出 47 备注 40%的数据n,m300 100%的数据n,m3000 思路 1、分析路可以重复走想到强连通分量如果强连通分量里面有一个点被访问那么整个强连通分量都要被访问否则答案偏小于是先tarjan再缩点 2、缩点之后整个图由一个有向有环图变为一个有向无环图于是spfa处理,然后就AC了机智如我╮(╯3╰)╭ 代码 1 #includeiostream2 #includecstdio3 #includestring4 #includecstring5 #includevector6 #includealgorithm7 #includequeue8 #includestack9 #define maxn 300510 #define maxint ~0U111 using namespace std;12 stackint sta;13 vectorint comp[maxn];14 int incomp[maxn],instack[maxn],dfn[maxn],low[maxn];15 int index,cnum;16 int n,m,q,d[maxn],rice[maxn],noodle[maxn],v[maxn],s,p,ans;17 vectorint g[maxn],nowg[maxn];18 int nowrice[maxn],nownoodle[maxn],nows;19 void input(){20 cinnm;21 int u,v;22 for(int i 1;i m;i){23 scanf(%d%d,u,v);24 g[u].push_back(v);25 26 }27 for(int i 1;i n;i){28 scanf(%d,rice[i]);29 }30 cinsp;31 int nnow;32 for(int i 1;i p;i){33 scanf(%d,nnow);34 noodle[nnow] 1;35 }36 }37 void tarjan(int u){38 instack[u] 2;39 dfn[u] low[u] index;40 sta.push(u);41 for(int i 0;i g[u].size();i){42 int j g[u][i];43 if(!dfn[j]){44 tarjan(j);45 low[u] min(low[u],low[j]);46 }else if(instack[j] 2){47 low[u] min(low[u],dfn[j]);48 }49 }50 if(dfn[u] low[u]){51 cnum;52 while(!sta.empty()){53 int t sta.top();54 sta.pop();55 instack[t] 1;56 incomp[t] cnum;57 comp[cnum].push_back(t);58 if(t u){59 break;60 }61 }62 }63 }64 void work(){65 for(int i 1;i n;i){66 if(!dfn[i]) tarjan(i);67 }68 int u,v,newu,newv;69 for(int i 1;i n;i){70 u i;71 newu incomp[u];72 nowrice[newu] rice[u];73 if(noodle[u]) nownoodle[newu] 1;74 if(u s) nows newu;75 for(int j 0;j g[u].size();j){76 v g[u][j];77 newv incomp[v];78 if(newu newv) continue;79 nowg[newu].push_back(newv);80 }81 }82 }83 void spfa(){84 queueint q;85 d[nows] nowrice[nows];86 v[nows] 1;87 q.push(nows);88 int xx,dd,to,wei;89 while(!q.empty()){90 xx q.front();91 dd d[xx];92 q.pop();93 v[xx] 0;94 if(nownoodle[xx]) ans max(ans,dd);95 for(int i 0;i nowg[xx].size();i){96 to nowg[xx][i];97 wei nowrice[to];98 if(dd wei d[to]){99 d[to] dd wei;
100 if(!v[to]){
101 v[to] 1;
102 q.push(to);
103 }
104 }
105 }
106 }
107 coutans;
108 }
109 int main(){
110 input();
111 work();
112 spfa();
113 return 0;
114 } View Code Tyvj 1202 数数食物链 描述 TsyD学习了生物的生态环境那一张后老师留了一项作业就是给一张食物网求所有食物链的总数。从最低营养级生物它不能吃任何其他的生物开始到最高营养级它不能被任何其他生物吃 叫做一条食物链输入保证所有的生物之间都有直接或间接的生存关系 输入格式 第一行 N,M 分别表示有NN50000个生物M(M100000)个吃的关系接下来M行 每行有两个值ab 分别 表示b吃a 编号从1开始 输出格式 食物链的总数 MOD 11129 的值 测试样例1 输入 3 3 1 2 2 3 1 3 输出 2 备注 样例解释两条食物链分别为 1-3 1-2-3 思路 拓扑排序找到入度为0的点然后dp 代码 1 #includeiostream2 #includecstdio3 #includecstring4 using namespace std;5 int out[50010],G[50010][310],in[50010];//出度邻接表 从1开始6 int n,m;7 int f[50010];//f[k]表示k到顶端共有多少条链8 void dfs(int k)9 {
10 if(out[k]0)//顶端
11 {
12 f[k]1;
13 return ;
14 }
15 for(int i1;iout[k];i)
16 {
17 if(f[G[k][i]]0) dfs(G[k][i]);
18 f[k](f[k]f[G[k][i]])%11129;
19 }
20 }
21 int main()
22 {
23 while(scanf(%d%d,n,m)2)
24 {
25 memset(out,0,sizeof(out));
26 memset(G,0,sizeof(G));
27 memset(f,0,sizeof(f));
28 memset(in,0,sizeof(in));
29 while(m--)
30 {
31 int x,y;scanf(%d%d,x,y);
32 out[x];in[y];
33 G[x][out[x]]y;
34 }
35 int cnt0;
36 for(int i1;in;i)
37 {
38 if(in[i]0)
39 {
40 dfs(i);
41 cnt(cntf[i])%11129;
42 }
43 }
44 printf(%d,cnt);
45 }
46 return 0;
47 } View Code Wikioi 3731 寻找道路 题目描述 Description 在有向图G中每条边的长度均为1现给定起点和终点请你在图中找一条从起点到终点的路径该路径满足以下条件 1路径上的所有点的出边所指向的点都直接或间接与终点连通。 2在满足条件1的情况下使路径最短。 注意图G中可能存在重边和自环题目保证终点没有出边。 请你输出符合条件的路径的长度。 输入描述 Input Description 第一行有两个用一个空格隔开的整数n和m表示图有n个点和m条边。 接下来的m行每行2个整数x、y之间用一个空格隔开表示有一条边从点x指向点y。 最后一行有两个用一个空格隔开的整数s、t表示起点为s终点为t。 输出描述 Output Description 输出文件名为road.out。 输出只有一行包含一个整数表示满足题目描述的最短路径的长度。如果这样的路径不存在输出-1。 样例输入 Sample Input road.in road.out 3 2 1 2 2 1 1 3 1 样例输出 Sample Output road.in road.out 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 3 数据范围及提示 Data Size Hint 对于30%的数据0 n ≤100 m ≤20 对于60%的数据0 n ≤1000 m ≤2000 对于100%的数据0 n ≤10,0000 m ≤200,0000 x,y,s,t≤nx≠t。 思路 分析问题做的最短路中的点既能从起点出发又能从终点回来所以先预处理有两种方式可以先在起点进行一遍bfs把在没到终点前就没有出边的点标记下然后再沿着反图进行一遍bfs或者可以直接从终点出发在反图进行一遍bfs把没涉及到的点标出来然后再在反图bfs最后最短路 代码 1 #includecstdio2 #includeiostream3 #includecstring4 #includestring5 #includealgorithm6 7 using namespace std;8 9 const int maxn 200005,maxnum 100000;10 int dist[maxn],jud[maxn],q[maxn],start[maxn],tnum[maxn],fjud[maxn],cuter[maxn],n,m,x,t,ans,num 0;11 12 struct star{13 int next;14 int to;15 int p;16 };17 star edge[maxn];18 19 void dfs(int node){20 int head 1,tail 1,bq[maxn];21 fjud[node] 0;22 bq[1] node;23 while(head tail){24 int now bq[head];25 for(int i start[now];i ! -1;i edge[i].next){26 if(fjud[edge[i].to]){27 tail (tail 1) % maxn;28 bq[tail] edge[i].to;29 fjud[edge[i].to] 0;30 }31 }32 head (head 1) % maxn;33 }34 }35 36 void dfs1(int node){37 int head 1,tail 1,bq[maxn];38 cuter[node] 0;39 bq[1] node;40 while(head tail){41 int now bq[head];42 for(int i start[now];i ! -1;i edge[i].next){43 if(cuter[edge[i].to]){44 bq[tail] edge[i].to;45 cuter[edge[i].to] 0;46 }47 }48 head (head 1) % maxn;49 }50 }51 52 int spfa(int u,int v){53 dist[u] jud[u] 0;54 q[1] u;55 int head 1,tail 1;56 while(head tail){57 int now q[head];58 for(int i start[now];i ! -1;i edge[i].next){59 60 if(dist[edge[i].to] dist[now] edge[i].p cuter[edge[i].to]){61 dist[edge[i].to] dist[now] edge[i].p;62 if(jud[edge[i].to]){63 tail (tail 1) % maxn;64 q[tail] edge[i].to;65 jud[edge[i].to] 0;66 }67 }68 }69 70 head (head 1) % maxn;71 jud[now] 1;72 }73 if(dist[v] 100000) return -1;74 return dist[v];75 }76 77 int main(){78 cinnm;79 int u,v,p;80 for(int i 1;i n;i){81 start[i] -1;82 dist[i] maxnum;83 jud[i] 1;84 fjud[i] 1;85 cuter[i] 1;86 tnum[i] 0;87 88 }89 int cnt 1;90 for(int i 1;i m;i){91 cinuv;92 swap(u,v);93 edge[i].p 1;94 edge[i].to v;95 edge[i].nextstart[u];96 cnt;97 start[u] cnt - 1;98 tnum[u]; 99 }
100 cinxt;
101 dfs(t);
102 for(int i 1;i n;i) if(fjud[i]) dfs1(i);
103 cuter[x] cuter[t] 1;
104 ans spfa(t,x);
105 coutans;
106 return 0;
107 } View Code Wikioi 1009 产生数 题目描述 Description 给出一个整数 nn10^30) 和 k 个变换规则k15。 规则 一位数可变换成另一个一位数 规则的右部不能为零。 例如n234。有规则k2 2 5 3 6 上面的整数 234 经过变换后可能产生出的整数为包括原数: 234 534 264 564 共 4 种不同的产生数问题 给出一个整数 n 和 k 个规则。求出 经过任意次的变换0次或多次能产生出多少个不同整数。 仅要求输出个数。 输入描述 Input Description 键盘输人格式为 n k x1 y1 x2 y2 ... ... xn yn 输出描述 Output Description 屏幕输出格式为 一个整数满足条件的个数 样例输入 Sample Input 234 2 2 5 3 6 样例输出 Sample Output 4 思路floyd预处理一个数能变换成多少数 代码 1 #includeiostream2 #includecstdio3 #includecstring4 #includestring5 #includecstdlib6 #includealgorithm7 8 using namespace std;9
10 const int maxn 1000;
11 char temp[maxn];
12 int edge[maxn][maxn],cou[maxn],n,k,big[maxn];
13
14 void init(){
15 cintempk;
16 n strlen(temp);
17 for(int i 0;i 9;i){
18 for(int j 0;j 9;j){
19 if(i j) edge[i][j] 1;
20 else edge[i][j] 0;
21 }
22 }
23 for(int i 0;i k;i){
24 int u,v;
25 cinuv;
26 edge[u][v] 1;
27 }
28 big[0] 1;
29
30 }
31
32 void fshort(){
33 for(int k 0;k 9;k){
34 for(int i 0;i 9;i){
35 if(i ! k){
36 for(int j 0;j 9;j)
37 if(j ! i j ! k (edge[i][k] edge[k][j])) edge[i][j] 1;
38
39 }
40 }
41 }
42 for(int i 0;i 9;i)
43 for(int j 0;j 9;j)
44 cou[i] edge[i][j];
45
46
47 }
48
49 void mplus(){
50 int ans 1,a,b 0;
51 for(int i 0;i n;i){
52 if(cou[temp[i] - 48]){
53 a cou[temp[i] - 48];
54 for(int j b;j 0;j--){
55 big[j] * a;
56 if(big[j] 9){
57 big[j 1] big[j] / 10;
58 big[j] big[j] % 10;
59 if(j b) b;
60 }
61 }
62 }
63
64 }
65 for(int j 0;j b;j){
66 if(big[j] 9){
67 big[j 1] big[j] / 10;
68 big[j] big[j] % 10;
69 if(j b) b;
70 }
71 }
72 for(int r b;r 0;r--)coutbig[r];
73 }
74
75
76 int main(){
77 init();
78 fshort();
79 mplus();
80 return 0;
81 } View Code 转载于:https://www.cnblogs.com/hyfer/p/4835169.html
