促销网站怎么做,鞍山网站页设计制作,wordpress singular,北京软件开发年薪A 去火车站 寒假到了#xff0c;小明准备坐火车回老家#xff0c;现在他从学校出发去火车站#xff0c;CC市去火车站有两种方式#xff1a;轻轨和公交车。小明为了省钱#xff0c;准备主要以乘坐公交为主。CC市还有一项优惠政策#xff0c;持学生证可以免费乘坐一站轻轨小明准备坐火车回老家现在他从学校出发去火车站CC市去火车站有两种方式轻轨和公交车。小明为了省钱准备主要以乘坐公交为主。CC市还有一项优惠政策持学生证可以免费乘坐一站轻轨但只能乘坐一站。小明想尽快到达火车站请编写程序为小明找到一条从学校到火车站最快的路线及换乘轻轨的方案。 假设换乘时间忽略不计公交车与轻轨站点相同但线路和速度不一定相同所有线路都是双向的。可以第一站就乘坐轻轨也可以最后一站乘坐轻轨也可以在中间某站坐轻轨。如果乘坐轻轨和不乘坐轻轨到达火车站的时间相同则无需换乘轻轨。最多坐一站轻轨。 输入格式: 输入包含多组数据。每组数据第一行为3个整数n、s和t分别表示车站数编号为1至n小明学校所在的站和火车站所在的站。下一行为一个整数m表示公交车的线路信息接下来m行每行为3个正整数a、b、c表示公交车从a站到b站需要c分钟。下一行为一个整数k表示轻轨的线路信息接下来k行每行为3个正整数x、y、z表示轻轨从x站到y站需要z分钟。所有整数均不超过20000。 输出格式: 对每组数据输出2行。第1行为1个整数T表示从学校到达火车站的最短时间第2行为一个整数K表示在站点K换乘轻轨若有多个可能的换乘点则输出编号最小者如果无需换乘轻轨则第二行输出“no metro”。 输入样例: 4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3 输出样例: 5
2
5
2 思路 这里给出两种做法第一种就是老师题解的思路正反跑一遍然后一一比较大小差异。。 我们可以思考一下假设不是走1条轻轨而是k条轻轨这道题该怎么做。写题稍微多一点的朋友肯定知道k条边限制的题一般都是用分层图最短路去写感兴趣的朋友可以去看看我写的另一篇博文分层图最短路感觉有点像拆点也有点像dp。。 法一 #includebits/stdc.h
using namespace std;
const int N 20010;
typedef pairint, intPII;
int h[2*N], e[2*N], w[2*N], ne[2*N], idx;
int dis1[N], dis2[N];
bool st1[N], st2[N];
bool flag;
int ans, cnt;
int n, m, k, s, t;
void init()
{ans 0x3f3f3f3f;cnt 0x3f3f3f3f;flag 1;idx 0;memset(st1, false, sizeof st1);memset(dis1, 0x3f, sizeof dis1);memset(dis2, 0x3f, sizeof dis2);memset(st2, false, sizeof st2);memset(h, -1, sizeof h);memset(e, 0, sizeof e);memset(w, 0, sizeof w);memset(ne, 0, sizeof ne);
}
void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}
void dijkstral(int u,int dis[],bool st[]) {priority_queuePII, vectorPII, greaterPIIq;q.push({ 0,u });dis[u] 0;while (q.size()) {auto p q.top();q.pop();int v p.second;if (st[v]) {continue;}st[v] true;for (int i h[v];~i;i ne[i]) {int j e[i];if (st[j]) {continue;}if (dis[j] dis[v] w[i]) {dis[j] dis[v] w[i];q.push({ dis[j],j});}}}
}
void solve()
{while (cin n s t) {init();cin m;for (int i 1;i m;i) {int a, b, c;cin a b c;add(a, b, c);add(b, a, c);}dijkstral(s,dis1,st1);dijkstral(t, dis2, st2);ans dis1[t];cin k;for (int i 1;i k;i) {int a, b, c;cin a b c;if (dis1[a] c dis2[b] ans) {flag 0;ans dis1[a] c dis2[b];cnt a;}else if (dis1[a] c dis2[b] ans) {cnt min(a, cnt);}if (dis1[b] c dis2[a] ans) {flag 0;ans dis1[b] c dis2[a];cnt b;}else if (dis1[b] c dis2[a] ans) {cnt min(cnt, b);}}if (flag) {cout dis1[t] endl;cout no metro endl;}else {cout ans endl;cout cnt endl;}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
} 法二 #includebits/stdc.h
using namespace std;
const int N 20010, M 40010;
typedef pairint, pairint, intPII;
int h[N], e[M], ne[M], w[M], idx;
int h2[N], e2[M], ne2[M], w2[M], idx2;
int dis[N][2];
bool st[N][2];
int cnt[N];
int n, m, k, s, t;
int ans;
int f;
void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}
void add2(int a, int b, int c) {e2[idx2] b, w2[idx2] c, ne2[idx2] h2[a], h2[a] idx2;
}
void dij()
{memset(dis, 0x3f, sizeof dis);memset(st, false, sizeof st);priority_queuePII, vectorPII, greaterPIIq;q.push({ 0,{s,0} });dis[s][0] 0;while (q.size()) {auto p q.top();q.pop();int v p.second.first;int u p.second.second;if (st[v][u]) {continue;}st[v][u] true;for (int i h[v];~i;i ne[i]) {int j e[i];if (st[j][u]) {continue;}if (dis[j][u] dis[v][u] w[i]) {if (u 1) {cnt[j] cnt[v];}dis[j][u] dis[v][u] w[i];q.push({ dis[j][u],{j,u} });}}if (u 1 1) {for (int i h2[v];~i;i ne2[i]) {int j e2[i];if (st[j][u 1]) {continue;}if (dis[j][u 1] dis[v][u] w2[i]) {dis[j][u 1] dis[v][u] w2[i];cnt[j] v;q.push({ dis[j][u 1],{j,u 1} });}else if (dis[j][u 1] dis[v][u] w2[i]) {cnt[j] min(cnt[j], v);//q.push({ dis[j][u 1],{j,u 1} });}}}}
}
void solve()
{while (cin n s t) {idx 0;idx2 0;f 0x3f3f3f3f;ans 0x3f3f3f3f;memset(cnt, 0x3f, sizeof cnt);memset(e, 0, sizeof e);memset(ne, 0, sizeof ne);memset(w, 0, sizeof w);memset(h, -1, sizeof h);memset(e2, 0, sizeof e2);memset(ne2, 0, sizeof ne2);memset(w2, 0, sizeof w2);memset(h2, -1, sizeof h2);cin m;for (int i 1;i m;i) {int a, b, c;cin a b c;add(a, b, c);add(b, a, c);}cin k;for (int i 1;i k;i) {int a, b, c;cin a b c;add2(a, b, c);}dij();if (dis[t][0] dis[t][1]) {cout dis[t][0] endl;cout no metro endl;}else {cout dis[t][1] endl;cout cnt[t] endl;}}}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
} B 联盟数目 艾迪是一家集团公司的老板该集团包含n家公司为了管理公司艾迪会时常通过网络向各公司发送消息。各公司间的网络是单向的每个公司都有一个分发列表表示其能向哪些公司直接传达消息。例如A公司的分发列表为B、C表示A可将消息直接传送给B和C由于网络是单向的B或C不一定能向A传送消息这样艾迪若想向A、B、C公司发送消息则只需向A发送消息即可随后A可将消息传送到B和C。 为了便于管理各公司艾迪打算将n家公司分成若干组每组称为一个区域联盟每组满足如下条件组内的任意公司消息互相可达。即对于组内任意公司u和vu可将消息传送到v可由u直接传送到v也可通过组内其他公司中转传送到vv也可将消息传送到u。可以认为一个公司可以将消息传送给自己即一个公司可以自成一组。 艾迪希望组的数量尽可能少即在满足上述条件的情况下每组包含的公司数目尽可能多。 现给定每个公司的分发列表请编写程序告知艾迪他的集团最少能分成多少组。 输入格式: 第一行包含一个整数T (1≤T≤100)表示数据组数。对于每组数据第一行为一个整数n (2≤n≤100)表示公司数目公司编号为1到n。随后n行第i行包含若干整数表示第i个公司的分发列表每行以0结尾。 输出格式: 对于每组数据输出一行为一个整数表示组数。 输入样例: 3
5
2 4 3 0
4 5 0
0
0
1 0
3
2 0
0
2 1 0
3
2 0
3 0
0 输出样例: 3
3
3 思路 这题我们依旧提供两种方法一个是Floyd一个是tarjan。 讲真的我以前真不知道Floyd可以求强连通分量。。 可能是n3次方太可拍了。。 Floyd #includebits/stdc.h
using namespace std;
const int N 110;
int dis[N][N];
bool st[N];
int n;
int ans;
void init()
{memset(dis, 0x3f, sizeof dis);memset(st, false, sizeof st);ans 0;for (int i 1;i n;i) {dis[i][i] 0;}
}
void solve()
{cin n;init();for (int i 1;i n;i) {int k;while (cin k k ! 0) {dis[i][k] 1;}}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];}}}}for (int i 1;i n;i) {if (st[i]) {continue;}st[i] true;for (int j i 1;j n;j) {if (st[j]) {continue;}if (dis[i][j] ! 0x3f3f3f3f dis[j][i] ! 0x3f3f3f3f) {st[j] true;}}ans;}cout ansendl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin T;while (T--) {solve();}return 0;
}tarjan #includebits/stdc.h
using namespace std;
const int N 110, M N * N;
int h[N], e[M], ne[M], idx;
int scc_cnt, id[N], _size[N];
int dfn[N], low[N];
int stk[N], top;
bool in_stk[N];
int timestamp;
int n;
void init()
{timestamp 0;scc_cnt 0;top 0;idx 0;memset(h, -1, sizeof h);memset(e, 0, sizeof e);memset(ne, 0, sizeof ne);memset(id, 0 ,sizeof id);memset(_size, 0, sizeof _size);memset(dfn, 0, sizeof dfn);memset(stk, 0, sizeof stk);memset(low, 0, sizeof low);memset(in_stk, false, sizeof in_stk);
}
void add(int a, int b) {e[idx] b, ne[idx] h[a];h[a] idx;
}void tarjan(int u)
{dfn[u] low[u] timestamp;stk[top] u, in_stk[u] true;for (int i h[u];i ! -1;i ne[i]){int j e[i];if (!dfn[j]) {tarjan(j);low[u] min(low[u], low[j]);}else if (in_stk[j]) {low[u] min(low[u], low[j]);}}if (dfn[u] low[u]) {int y;scc_cnt;do {y stk[top--];in_stk[y] false;id[y] scc_cnt;_size[scc_cnt];} while (u ! y);}
}void solve()
{init();cin n;for (int i 1;i n;i) {int k -1;while (cin k k ! 0) {add(i, k);}}for (int i 1;i n;i) {if (dfn[i]) {continue;}else {tarjan(i);}}cout scc_cnt endl;}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin T;while (T--) {solve();}return 0;
} 这里的tarjan不需要这么麻烦我只是写一个模板写多了。。 C 社交网络 可以将n个QQ用户间的好友关系建模为一个包含n个顶点的无向图顶点编号为1至n每个顶点对应一个用户若2个用户i和j是QQ好友则在顶点i和j之间连接一条边并根据用户间的亲密度对该边附以一个权值cij。在该图中可以利用两个顶点间的最短路径长度衡量两个用户的关系密切程度也可以利用经过一个顶点的最短路径数目来衡量一个用户在关系网络中的影响力具体地我们定义用户k在QQ关系网络中的“影响力”为 其中Nij为顶点i到j的最短路径数目Nijk为顶点i到j的所有最短路径中经过顶点k的最短路径数目上述二值可能超出int型范围请使用long long类型。Dij表示i到j的最短路径长度。 现给定一个如上描述的无向图请编写程序计算每个顶点的“影响力”假定给定的图是连通的。 输入格式: 输入第一行为两个正整数n和e分别表示图的顶点数和边数接下来e行表示每条边的信息每行为3个正整数a、b、c其中a和b表示该边的端点编号c表示权值。各边并非按端点编号顺序排列。 n≤100e≤5000c≤1000任意两点间的最短路径数目≤1010 输出格式: 输出为n行每行一个实数精确到小数点后3位第i行为顶点i的影响力。 输入样例: 4 4
3 2 6
4 3 1
1 3 9
4 1 1 输出样例: 0.000
0.000
30.000
20.000 解释: 对于顶点1边2-3、3-4、2-4的最短路径均不经过顶点1故顶点1的影响力为0. 对于顶点3 顶点1到2的最短路径共1条长度为8经过点3顶点2到4的最短路径共1条长度为7经过点3顶点1到4的最短路径共1条但不经过点3。 故f(3)D12∗1D24∗1D14∗0D21∗1D42∗1D41∗087087030.000 提示: 若顶点a到顶点b有x条路径点b到点c有y条路径则a经过b到达c的路径有x*y条。 思路 这题是最简单的有没有人同感。。 就是简单的dijktra。。 只是一定要小心longlong相乘会越界改成double就好了。 #includebits/stdc.h
using namespace std;
const int N 110, M 10010;
typedef long long LL;
typedef pairLL, intPII;
LL dis[N][N];
bool st[N][N];
int h[N], e[M], ne[M], w[M], idx;
LL cnt[N][N];
int n, m;
double ans[N];
void add(int a, int b, int c) {e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}
void dijkstral(int u) {priority_queuePII, vectorPII, greaterPIIq;q.push({ 0,u });dis[u][u] 0;cnt[u][u] 1;while (q.size()) {auto t q.top();q.pop();int v t.second;if (st[u][v]) {continue;}st[u][v] true;for (int i h[v];~i;i ne[i]) {int j e[i];if (st[u][j]) {continue;}if (dis[u][j] dis[u][v] w[i]) {dis[u][j] dis[u][v] w[i];cnt[u][j] cnt[u][v];q.push({ dis[u][j],j});}else if (dis[u][j] dis[u][v]w[i]) {cnt[u][j] cnt[u][v];q.push({ dis[u][j],j});}}}
}
void solve()
{cin n m;memset(st, false, sizeof st);memset(h, -1, sizeof h);memset(dis, 0x3f, sizeof dis);for (int i 1;i m;i) {int a, b, c;cin a b c;add(a, b, c);add(b, a, c);}for (int i 1;i n;i) {dijkstral(i);}for (int i 1;i n;i) {for (int j 1;j n;j) {for (int k 1;k n;k) {//cout dis[j][k] endl;//cout cnt[j][k] endl;if (j i || k i) {continue;}if (dis[j][k] 0x3f3f3f3f||dis[j][i]0x3f3f3f3f||dis[i][k]0x3f3f3f3f) {continue;}if (cnt[j][i] 0 || cnt[i][k]0) {continue;}if (dis[j][k] ! dis[j][i] dis[i][k]) {continue;}//cout i j k endl;double x cnt[j][i] * cnt[i][k];double y x / cnt[j][k];ans[i] y * dis[j][k];}}}for (int i 1;i n;i) {cout fixed setprecision(3) ans[i] endl;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}
