首页 > 代码库 > Codeforces449A Jzzhu and Chocolate && 449B Jzzhu and Cities
Codeforces449A Jzzhu and Chocolate && 449B Jzzhu and Cities
CF挂0了,简直碉堡了。两道题都是正确的思路但是写残了。写个解题报告记录一下心路历程。
A题问的是 一个n*m的方块的矩形上切k刀,最小的那一块最大可以是多少。不难发现如果纵向切k1刀,横向切k2刀,那么答案应该是 (n/(k1+1)) * (m/(k2+1)),除法是取整的。虽然是取整,但是不难发现其实就是要(k1+1)*(k2+1)最小,根据均值不等式,k1+k2=k(定值) k1==k2的时候(k1+1)*(k2+1)=k1*k2+k1+k2+1=k1*k2+k+1应该是取最大值,所以当k1,k2越接近两端的时候这个值才会最小,所以我们总是先把某一维的切掉,然后再考虑剩下那一维。比赛的时候手残写错了,哎。。。
B题问的是给你一个图,一些是普通边,一些是train route边,train route边是从首都1连到其它点的,问的是train route边最多可以去掉多少条使得每个点的最短路径长不变。思路就是如果某个点我们可以通过走别的点到达的话,那么这条边是不需要的,留边的时候更新ans我写漏了,导致答案小了很多。
#pragma warning(disable:4996)#include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <queue>using namespace std;#define ll long long#define maxn 105000#define inf 10000000000000000LLint n, m, k;struct Edge{ int v; ll w; Edge(int vi, ll wi) : v(vi), w(wi){} Edge(){}};vector<Edge>G[maxn];ll dis2[maxn];ll ans = 0;ll d[maxn];bool in[maxn];void spfa(){ memset(d, 0x3f, sizeof(d)); memset(in, 0, sizeof(in)); queue<int> que; que.push(1); in[1] = true; d[1] = 0; while (!que.empty()){ int u = que.front(); que.pop(); in[u] = false; for (int i = 0; i < G[u].size(); i++){ int v = G[u][i].v; ll w = G[u][i].w; if (d[u] + w < d[v]){ d[v] = d[u] + w; if (!in[v]) que.push(v), in[v] = true; } } }}ll d2[maxn];bool upd[maxn];void spfa2(){ memset(d2, 0x3f, sizeof(d2)); memset(in, 0, sizeof(in)); queue<int> que; que.push(1); d2[1] = 0; in[1] = true; for (int i = 2; i <= n; i++){ if (dis2[i] < d[i]){ que.push(i); in[i] = true; d2[i] = dis2[i]; } } while (!que.empty()){ int u = que.front(); que.pop(); in[u] = false; for (int i = 0; i < G[u].size(); i++){ int v = G[u][i].v; ll w = G[u][i].w; if (d2[u] + w < d2[v]){ d2[v] = d2[u] + w; if (!in[v]) que.push(v), in[v] = true; if (upd[v]) { ++ans; upd[v] = false; } } else if (d2[u] + w == d2[v]){ if (upd[v]) { ++ans; upd[v] = false; } } } }}int main(){ while (cin >> n >> m >> k){ for (int i = 0; i <= n; i++) G[i].clear(); memset(dis2, 0x3f, sizeof(dis2)); ans = 0; int ui, vi; ll wi; for (int i = 0; i < m; i++){ scanf("%d%d%I64d", &ui, &vi, &wi); G[ui].push_back(Edge(vi, wi)); G[vi].push_back(Edge(ui, wi)); } spfa(); memcpy(dis2, d, sizeof(dis2)); memset(upd, 0, sizeof(upd)); int si; ll yi; for (int i = 0; i < k; i++){ scanf("%d%I64d", &si, &yi); if (dis2[si] <= yi) ++ans; else { dis2[si] = yi; if (upd[si]) { ++ans; } upd[si] = true; } } spfa2(); cout << ans << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。