暑假集训专题练习记录——最小生成树 最短路

最小生成树和最短路

• 题目列表
• • A Jungle Roads（POJ1251)
  • B Networking（POJ1287）
  • C Building a Space Station（POJ2031）
  • D Constructing Roads（POJ2421）
  • E Truck History（POJ1789）
  • F Arctic Network（POJ2349）
  • G Highways（POJ1751）
  • H Til the Cows Come Home（POJ2387）
  • I Frogger（POJ2253）
  • J Heavy Transportation（POJ1797）
  • K Silver Cow Party（POJ3268）
  • L Currency Exchange（POJ1860）
  • M Wormholes（POJ3259）
  • N MPI Maelstrom（POJ1502）
  • O Cow Contest（POJ3660）
  • P Arbitrage （POJ2240）
• 总结

题目列表

A Jungle Roads（POJ1251)

最小生成树板子题，直接套板子就能过。

AC代码

#include 
#include 
#include using namespace std;
const int max_n = 1e5;
int parent[max_n];
int myRank[max_n];void init(int n)
{for (int i = 0; i < n; i++){parent[i] = i;myRank[i] = 0;}
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}void unite(int x, int y)
{x = find(x);y = find(y);if (x == y)return;if (myRank[x] < myRank[y]){parent[x] = y;}else{parent[y] = x;if (myRank[x] == myRank[y]){myRank[x]++;}}
}bool same(int x, int y)
{return find(x) == find(y);
}struct edge
{int stN, edN, cost;bool operator<(edge e1){return this->cost < e1.cost;}
} edges[max_n];int krukal(int v, int e)
{sort(edges, edges + e);init(v);int res = 0;int nedge = 0;for (int i = 0; i < e && nedge != v - 1; i++){edge et = edges[i];if (!same(et.stN, et.edN)){unite(et.stN, et.edN);res += et.cost;nedge++;}}if (nedge < v - 1)res = -1;return res;
}int main()
{int n, index;while (cin >> n){if (n == 0)break;cin >> index;for (int i = 0; i < index; i++)cin >> edges[i].stN >> edges[i].edN >> edges[i].cost;int ans = krukal(n, index);cout << ans << endl;}return 0;
}

B Networking（POJ1287）

还是板子题，没有什么需要注意的地方。

AC代码

#include 
#include 
#include using namespace std;
const int max_n = 1e5;
int parent[max_n];void init(int n)
{for (int i = 0; i < n + 10; i++)parent[i] = i;
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}void unite(int x, int y)
{x = find(x);y = find(y);if (x == y)return;parent[x] = y;
}bool same(int x, int y)
{return find(x) == find(y);
}struct edge
{int stN, edN, cost;bool operator<(edge e1){return this->cost < e1.cost;}
} edges[max_n];int krukal(int v, int e)
{sort(edges, edges + e);init(v);int res = 0;int nedge = 0;for (int i = 0; i < e && nedge != v - 1; i++){edge et = edges[i];if (!same(et.stN, et.edN)){unite(et.stN, et.edN);res += et.cost;nedge++;}}if (nedge < v - 1) //不连通res = -1;return res;
}int main()
{//点数 边数int n, index;while (cin >> n){if (n == 0)break;cin >> index;for (int i = 0; i < index; i++)cin >> edges[i].stN >> edges[i].edN >> edges[i].cost;int ans = krukal(n, index);cout << ans << endl;}return 0;
}

C Building a Space Station（POJ2031）

题目大意：
求对立体中求得最小生成树。
思路:
先处理出来边，两个球如果相交了那么代表这条边得权值为0。然后求所有边得最小生成树就行了。

AC代码

#include 
#include 
#include 
#include using namespace std;
const int max_n = 1e4;struct pp
{int index;double x, y, z, r;
};double cost(pp p1, pp p2)
{double ans = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y) + (p2.z - p1.z) * (p2.z - p1.z)) - (p1.r + p2.r);return ans > 0 ? ans : 0;
}int parent[max_n];
vector<pp> vp;struct edge
{int stN, edN;double co;bool operator<(edge e){return co - e.co < 0;}
} edges[max_n];void init(int n)
{for (int i = 0; i < n; i++)parent[i] = i;
}
int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}void unit(int x, int y)
{x = find(x);y = find(y);if (x == y)return;parent[x] = y;
}
bool same(int x, int y)
{return find(x) == find(y);
}int main()
{int n;while (cin >> n){if (n == 0)break;vp.clear();for (int i = 0; i < n; i++){pp tmp;cin >> tmp.x >> tmp.y >> tmp.z >> tmp.r;tmp.index = i;vp.push_back(tmp);}int index = 0;for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){edges[index].stN = vp[i].index;edges[index].edN = vp[j].index;edges[index].co = cost(vp[i], vp[j]);index++;}}init(n);sort(edges, edges + index);double res = 0;int nedge = 0;for (int i = 0; i < index && nedge != n - 1; i++){edge e = edges[i];if (!same(e.stN, e.edN)){unit(e.stN, e.edN);res += e.co;nedge++;}}printf("%.3lf\n", res);}return 0;
}

D Constructing Roads（POJ2421）

题目大意：
给你一个邻接矩阵并且已知某些点已经连接好了，求最小生成树。
思路：
已经连好的点可以直接加入到并查集里面或者将 权值设为零。

AC代码

#include 
#include using namespace std;
int arr[200][200];
struct edge
{int stn, edn, cost;bool operator<(edge e){return cost < e.cost;}
} edges[10010];int parent[200];
void init(int n)
{for (int i = 1; i <= n; i++)parent[i] = i;
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}bool same(int x, int y)
{return find(x) == find(y);
}void unit(int x, int y)
{x = find(x);y = find(y);if (x != y)parent[x] = y;
}int kruskal(int n, int index)
{int nedge = 0;init(n);sort(edges, edges + index);int ans = 0;for (int i = 0; i < index && nedge < n - 1; i++){if (!same(edges[i].stn, edges[i].edn)){ans += edges[i].cost;unit(edges[i].stn, edges[i].edn);}}return ans;
}int main()
{int n;cin >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];int index = 0;for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){edges[index].stn = i;edges[index].edn = j;edges[index].cost = arr[i][j];index++;}}int m;cin >> m;for (int i = 0; i < m; i++){int a, b;cin >> a >> b;edges[index].stn = a;edges[index].edn = b;edges[index].cost = 0;index++;}int ans = kruskal(n, index);cout << ans << endl;return 0;
}

E Truck History（POJ1789）

题目大意：
已知n个长度为7的字符串，字符串与字符串之间的权值是字符串不同字符的个数。求最小生成树。
思路：
先预处理出来权值，在模板。

AC代码

#include 
#include 
#include 
#include using namespace std;
const int max_n = 2000 * 2000 + 10;
string ss[2020];struct edge
{int stn, edn, cost;bool operator<(edge e){return cost < e.cost;}
} ve[max_n];int getCost(string a, string b)
{int sum = 0;for (int i = 0; i < 7; i++){if (a[i] != b[i])sum++;}return sum;
}int parent[2010];void init(int n)
{for (int i = 0; i < n; i++)parent[i] = i;
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}bool same(int x, int y)
{return find(x) == find(y);
}void unit(int x, int y)
{x = find(x);y = find(y);if (x != y)parent[x] = y;
}int kruskal(int n, int index)
{int nedge = 0;init(n);sort(ve, ve + index);int ans = 0;for (int i = 0; i < index && nedge < n - 1; i++){if (!same(ve[i].stn, ve[i].edn)){ans += ve[i].cost;unit(ve[i].stn, ve[i].edn);nedge++;}}if (nedge < n - 1)ans = -1;return ans;
}int main()
{int n;while (cin >> n){if (n == 0)break;for (int i = 0; i < n; i++)cin >> ss[i];int index = 0;for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){ve[index].stn = i;ve[index].edn = j;ve[index].cost = getCost(ss[i], ss[j]);index++;}}int ans = kruskal(n, index);cout << "The highest possible quality is 1/" << ans << "." << endl;}return 0;
}

F Arctic Network（POJ2349）

题目大意：
有n个前哨，使用无线电通信或者卫星都可以将他们联通。卫星无视距离。
现给出卫星的数目和每个前哨的坐标，让求两前哨可以无线电通信的最小权值。
思路：
先预处理所有的边，然后求最小生成树。
求的同时记录所有的权值，求完之后排序将大的边用卫星，剩下边的最大值就是所求。
对边的处理上，刚开始不用直接开方，可以都用整型的，最后输出答案时再开方。

AC代码

#include 
#include 
#include 
using namespace std;const int max_n = 500 * 500 + 10;struct edge
{int stn, edn, cost;bool operator<(edge e){return cost < e.cost;}
} edges[max_n];pair<int, int> pii[1000];int parent[1000];
void init(int n)
{for (int i = 0; i < n; i++)parent[i] = i;
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}bool same(int x, int y)
{return find(x) == find(y);
}void unit(int x, int y)
{x = find(x);y = find(y);if (x != y)parent[x] = y;
}int ans[1000];
bool cmp(int a, int b)
{return a > b;
}void kruskal(int n, int index, int s)
{init(n);sort(edges, edges + index);int nedge = 0;for (int i = 0; i < index && nedge < n - 1; i++){if (!same(edges[i].stn, edges[i].edn)){unit(edges[i].stn, edges[i].edn);ans[nedge] = edges[i].cost;nedge++;}}sort(ans, ans + nedge, cmp);printf("%.2lf\n", sqrt(1.0 * ans[s - 1]));
}int getCost(pair<int, int> p1, pair<int, int> p2)
{return (p1.first - p2.first) * (p1.first - p2.first) + 1.0 * (p1.second - p2.second) * (p1.second - p2.second);
}int main()
{int T;cin >> T;while (T--){int s, p;cin >> s >> p;for (int i = 0; i < p; i++)cin >> pii[i].first >> pii[i].second;int index = 0;for (int i = 0; i < p - 1; i++){for (int j = i + 1; j < p; j++){edges[index].stn = i;edges[index].edn = j;edges[index].cost = getCost(pii[i], pii[j]);index++;}}kruskal(p, index, s);}return 0;
}

G Highways（POJ1751）

题目大意：
给出n个点的坐标，其中m个点已经联通了，求其最小生成树剩余的联通情况（即哪个点和哪个点联通了）
思路：
预处理边，最小生成树。
如果已经联通，权值设为零。在最小生成树里面，联通两点的同时输出答案就行了。

AC代码

#include 
#include 
#include using namespace std;
const int max_n = 750 * 750 + 10 + 1000;pair<int, int> pii[max_n];
int getCost(pair<int, int> p1, pair<int, int> p2)
{return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}struct edge
{int stn, edn, cost;bool operator<(edge e){return cost < e.cost;}
} edges[max_n];int parent[1000];
void init(int n)
{for (int i = 1; i <= n; i++)parent[i] = i;
}int find(int x)
{if (x != parent[x])parent[x] = find(parent[x]);return parent[x];
}bool same(int x, int y)
{return find(x) == find(y);
}void unit(int x, int y)
{x = find(x);y = find(y);if (x != y)parent[x] = y;
}void kruskal(int n, int index)
{init(n);sort(edges, edges + index);for (int i = 0; i < index; i++){if (!same(edges[i].stn, edges[i].edn)){unit(edges[i].stn, edges[i].edn);if (edges[i].cost != 0)cout << edges[i].stn << " " << edges[i].edn << endl;}}
}int main()
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> pii[i].first >> pii[i].second;int index = 0;for (int i = 1; i <= n - 1; i++){for (int j = i + 1; j <= n; j++){edges[index].stn = i;edges[index].edn = j;edges[index].cost = getCost(pii[i], pii[j]);index++;}}int m;cin >> m;for (int i = 0; i < m; i++){int a, b;cin >> a >> b;edges[index].stn = a;edges[index].edn = b;edges[index].cost = 0;index++;}kruskal(n, index);return 0;
}

H Til the Cows Come Home（POJ2387）

最短路板子题。可以直接上Dijkstra。
不过当时wa了好多发，可能时板子的问题，其实现在也不是很清楚

AC代码

#include 
#include 
#include using namespace std;const int max_v = 1e4 + 10;int cost[max_v][max_v]; //权值
int d[max_v];           //从s出发最短距离
bool used[max_v];       //使用过的
int V;                  //顶点数void dijkstra()
{for (int i = 1; i <= V; i++){used[i] = false;d[i] = cost[1][i];}while (true){int v = -1;for (int u = 1; u <= V; u++){if (!used[u] && (v == -1 || d[u] < d[v]))v = u;}if (v == -1)break;used[v] = true;for (int u = 1; u <= V; u++){if (!used[u]) //注意要加这行！d[u] = min(d[u], d[v] + cost[v][u]);}}
}
int main()
{//点数 边数int n, index;while (cin >> index >> n){V = n;for (int i = 1; i <= V; i++){for (int j = 1; j <= V; j++){if (i != j)cost[i][j] = 1 << 30;elsecost[i][j] = 0;}}for (int i = 0; i < index; i++){int f, t, v;cin >> f >> t >> v;if (cost[f][t] > v){cost[f][t] = v;cost[t][f] = v;}}dijkstra();cout << d[n] << endl;}return 0;
}

I Frogger（POJ2253）

题目大意：
有n块石头的坐标，青蛙要从第1块跳到第2块。问青蛙最少跳多远就可以了（即求最短路中的最小权值）
思路：
因为数据量也不大，所以使用Floyd可以很好的解决这个问题。在更新路径的时候，如果I->K这段路大于I->J并且大于J-K，那么就应该选择I->J->K这条路让答案更小。

AC代码

#include 
#include 
#include 
#include using namespace std;const int max_n = 1e4;double cost[max_n][max_n];pair<int, int> pii[max_n];double getCost(pair<int, int> p1, pair<int, int> p2)
{return sqrt((double)(p1.first - p2.first) * (p1.first - p2.first) + (double)(p1.second - p2.second) * (p1.second - p2.second));
}int main()
{int n;int index = 1;while (cin >> n){if (n == 0)break;for (int i = 0; i < n; i++)cin >> pii[i].first >> pii[i].second;for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){cost[i][j] = getCost(pii[i], pii[j]);cost[j][i] = cost[i][j];}}for (int k = 0; k < n; k++){for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){// 如果ik kj 都小于ij 那么走“远路” i -> j - >kif (cost[i][k] < cost[i][j] && cost[k][j] < cost[i][j]){//ij更新为远路中的最大值if (cost[i][k] < cost[k][j])cost[i][j] = cost[j][i] = cost[k][j];elsecost[i][j] = cost[j][i] = cost[i][k];}}}}cout << "Scenario #" << index << endl;printf("Frog Distance = %.3f\n\n", cost[0][1]);index++;}return 0;
}

J Heavy Transportation（POJ1797）

题目大意：
有n个点，给出一些边的权值，求最短路最小边的最大值。
思路：
直接dijkstra，每次选择有最大的那个点。注意最后让输出两个换行！！！

AC代码

#include 
#include 
#include 
#include using namespace std;const int max_n = 1e4;
int cost[max_n][max_n];
pair<int, int> pii[max_n];int d[max_n];     //从s出发最短距离
bool used[max_n]; //使用过的
int V;            //顶点数
//从s出发到各个顶点的最短距离void dijkstra()
{for (int i = 1; i <= V; i++){used[i] = false;d[i] = cost[1][i];}while (true){int v = -1;for (int u = 1; u <= V; u++){if (!used[u] && (v == -1 || d[u] > d[v]))v = u;}if (v == -1)break;used[v] = true;for (int u = 1; u <= V; u++){if (!used[u] && d[u] < min(d[v], cost[v][u]))d[u] = min(d[v], cost[v][u]);}}
}
//最小边的最大值
int main()
{int T;cin >> T;int index = 1;while (T--){int n, m;cin >> n >> m;V = n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cost[i][j] = 0;}}for (int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;cost[a][b] = c;cost[b][a] = c;}dijkstra();cout << "Scenario #" << index << ":" << endl;cout << d[n] << endl<< endl;index++;}return 0;
}

K Silver Cow Party（POJ3268）

题目大意：
有n头牛要从自己家农场去指定农场参加派对，结束之后再回自己家农场，问花费的最长时间时多少。
各个农场之间有向边连接。
思路：
很容易想到算出去时的最短路，和回去时的最短路，然后相加取最大值就行了。但是数据量1e3跑floyd会T，如果对每个点都跑一次dijkstra也会T。
参考网上一名大佬的思路。
跑一遍dijkstra之后，置换矩阵，变成两个单源最短路。
第一遍求i->x，第二遍求x->i。
置换矩阵可以让边的方向改变。很好的减少了时间复杂度。

AC代码

#include 
#include 
#include using namespace std;const int max_v = 1e4 + 10;int cost[max_v][max_v]; //权值
int d[max_v];           //从s出发最短距离
int dx[max_v];
bool used[max_v]; //使用过的
int V;            //顶点数
//从s出发到各个顶点的最短距离int ans = 0;void dxx(int x)
{for (int i = 1; i <= V; i++){used[i] = false;dx[i] = cost[x][i];}while (true){int v = -1;for (int u = 1; u <= V; u++){if (!used[u] && (v == -1 || dx[u] < dx[v]))v = u;}if (v == -1)break;used[v] = true;for (int u = 1; u <= V; u++){if (!used[u])dx[u] = min(dx[u], dx[v] + cost[v][u]);}}
}
void dijkstra(int s)
{int sum = 0;for (int i = 1; i <= V; i++){used[i] = false;d[i] = cost[s][i];}while (true){int v = -1;for (int u = 1; u <= V; u++){if (!used[u] && (v == -1 || d[u] < d[v]))v = u;}if (v == -1)break;used[v] = true;for (int u = 1; u <= V; u++){if (!used[u])d[u] = min(d[u], d[v] + cost[v][u]);}}
}
int main()
{//点数 边数int n, m, x;cin >> n >> m >> x;V = n;for (int i = 1; i <= V; i++){for (int j = 1; j <= V; j++){if (i != j)cost[i][j] = 1 << 30;elsecost[i][j] = 0;}}for (int i = 0; i < m; i++){int f, t, v;cin >> f >> t >> v;cost[f][t] = v;}dxx(x);//矩阵置换，相当于把边反过来，那么从其他点到x的距离就是相当于是反过来后从x到其他点的距离for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++)swap(cost[i][j], cost[j][i]);}dijkstra(x);for (int i = 1; i <= n; i++)ans = max(ans, dx[i] + d[i]);cout << ans << endl;return 0;
}

L Currency Exchange（POJ1860）

题目大意：
给出n种货币，给出m种汇率和佣金情况，问是否可以通过多次操作，是自己原本的钱增加，最后还得是原本的货币种类。
思路：
寻找一个环，使得钱到自己这里的时候变多了。寻找环很容易想到bellman ford的算法。需要注意的是，货币的数目需要实时更新。还有就是边的储存方式。

AC代码

#include 
#include 
#include 
#include 
#include using namespace std;const int max_v = 1e3 + 10;
struct cur
{//a->b的汇率 佣金 b->a的汇率 佣金double rab, cab, rba, cba;void operator=(cur c){rab = c.rba;cab = c.cba;rba = c.rab;cba = c.cab;}
} curs[max_v][max_v];struct edge
{int from, to;double cost;
};edge es[max_v];
double d[max_v];
//v顶点数 e边数
int V, E;
int s;
double x;bool find_negative_loop()
{memset(d, 0, sizeof(d));d[s] = x;for (int i = 0; i < V; i++){for (int j = 0; j < E; j++){edge e = es[j];e.cost = d[e.from] - (d[e.from] - curs[e.from][e.to].cab) * curs[e.from][e.to].rab;if (d[e.to] < d[e.from] - e.cost){d[e.to] = d[e.from] - e.cost;if (i == V - 1) //存在负圈return true;}}}return false;
}int main()
{//货币种类数量 货币兑换条目 N有的种类 N有的数量int n, m;//最后s->scin >> n >> m >> s >> x;V = n;int index = 0;E = m;for (int i = 0; i <= n; i++){for (int j = 0; j <= n; j++){curs[i][j].cab = curs[i][j].cba = (1 << 30);curs[j][i] = curs[i][j];}}for (int i = 0; i < m; i++){int a, b;cin >> a >> b;cin >> curs[a][b].rab >> curs[a][b].cab >> curs[a][b].rba >> curs[a][b].cba;curs[b][a] = curs[a][b];es[index].from = a;es[index].to = b;es[index].cost = 1 << 30;index++;es[index].from = b;es[index].to = a;es[index].cost = 1 << 30;index++;}E = index;if (find_negative_loop()){cout << "YES" << endl;}else{cout << "NO" << endl;}return 0;
}

M Wormholes（POJ3259）

题目大意：
有n个农场，m个路径和w个虫洞，走路需要花时间，但是经过虫洞可以回到过去。问转一圈能否让自己回到过去。
思路：
数据量比较小可以采用比较好写的floyd，判断d[i][i]是否小于0就行。
注意要使用较快的输入输出方式。如果是cin需要关闭输入输出流，不然会T。

AC代码

#include 
#include 
#include 
#include 
#include #define endl '\n'
using namespace std;const int max_v = 1000 + 5;
const int INF = 0x3f3f3f3f;
int d[max_v][max_v];
int n, m, w;bool floyd()
{for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (d[i][j] > d[i][k] + d[k][j])d[i][j] = d[i][k] + d[k][j];}if (d[i][i] < 0)return true;}}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){memset(d, INF, sizeof(d));cin >> n >> m >> w;for (int i = 1; i <= n; i++)d[i][i] = 0;for (int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;if (d[a][b] > c)d[a][b] = d[b][a] = c;}for (int i = 0; i < w; i++){int a, b, c;cin >> a >> b >> c;d[a][b] = -c;}if (floyd())cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

N MPI Maelstrom（POJ1502）

题目大意：
给你邻接矩阵的下三角部分，x代表不连通，求最短路的最大边。
思路：
建议使用char*，这样可以直接使用atoi比较方便。
还有就是距离d要初始化为无穷大。这道题wa了20多发，因为没有初始化。

AC代码

#include 
#include 
#include 
#include 
#include using namespace std;const int max_v = 200 + 5;
const int INF = 0x3f3f3f3f;
int d[max_v][max_v];
int a[max_v][max_v];int main()
{memset(d, INF, sizeof(d));int n;cin >> n;for (int i = 2; i <= n; i++){for (int j = 1; j < i; j++){char s[100];cin >> s;if (s[0] == 'x')a[j][i] = a[i][j] = INF;elsea[j][i] = a[i][j] = atoi(s);}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j)d[i][j] = 0;elsed[i][j] = a[i][j];}}for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}int ans = 0;for (int i = 2; i <= n; i++)ans = max(ans, d[1][i]);cout << ans << endl;return 0;
}

O Cow Contest（POJ3660）

题目大意：
有n头会编程的牛（震惊）牛的编程等级决定了它的排名（卷起来了）现在让判断能够确定排名的牛有几头。
思路：
数据量较小，使用floyd。如果a能够打败b，则设为1，反之为0。最后统计自己能打败的和能打败自己的牛的数目。如果正好的牛的总数-1，那么自己的排名就确定了。

AC代码

#include 
#include 
#include 
#include using namespace std;const int max_n = 2e2;
const int INF = 0x3f3f3f3f;int d[max_n][max_n];int main()
{int n, m;cin >> n >> m;for (int i = 0; i < m; i++){int a, b;cin >> a >> b;d[a][b] = 1;}for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){//i能打败k k能打败j 那么i能打败jif (d[i][k] && d[k][j])d[i][j] = 1;}}}int ans = 0;for (int i = 1; i <= n; i++){int cnt = 0;for (int j = 1; j <= n; j++){//如果i能打败j 或者 j能打败iif (d[i][j] || d[j][i])cnt++;}if (cnt == n - 1)ans++;}cout << ans << endl;return 0;
}

P Arbitrage （POJ2240）

题目大意：
货币转换，问能否赚钱，和前面一道题很像。
思路：
使用map储存各个货币，将string变成int。初始化原本的钱为1，然后就直接floyd。需要注意的是，两个货币之间的传递需要汇率相乘。最后判断是否大于1就可以了。

AC代码

#include 
#include 
#include 
#include 
#include using namespace std;const int max_n = 1e3 + 100;
const int INF = 0x3f3f3f3f;double d[max_n][max_n];int main()
{int index = 1;int n;while (cin >> n){if (n == 0)break;memset(d, INF, sizeof(d));for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (i == j)d[i][j] = 1;elsed[i][j] = INF;}}map<string, int> mp;for (int i = 0; i < n; i++){string s;cin >> s;mp[s] = i;}int m;cin >> m;for (int i = 0; i < m; i++){string s1, s2;double r;cin >> s1 >> r >> s2;d[mp[s1]][mp[s2]] = r;}for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){d[i][j] = max(d[i][j], d[i][k] * d[k][j]);}}}cout << "Case " << index << ": ";for (int i = 0; i < n; i++){if (d[i][i] > 1){cout << "Yes" << endl;break;}else if (i == n - 1)cout << "No" << endl;}index++;}return 0;
}

总结

本专题收获非常的多，对kruskal和dijkstra还有floyd的理解更深了。做的时候经常会“wc，这个算法还能这么用”这种，明白了很多个变形。
对邻接矩阵的掌握程度不错，但是邻接表就不太行了。以后还是要多加练习。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！