首页 > 代码库 > Problem K: Yikes -- Bikes!
Problem K: Yikes -- Bikes!
http://acm.upc.edu.cn/problem.php?id=2780
昨天做的题，没过……！！！伤心……
题意：给你n个单位，n-1组关系，让你单位换算……
解题思路：Floyd算法
自己听别人说用Floyd算法，然后自己默默的用有向图写……但是！！！Floyd算法不能用有向图……！所以只能在其相反的转化中标记为负的，在进行时特殊处理一下，最后便利找出能进行单位转化的那组单位，然后进行大小排序，最后就莫名其妙的哦过了……！！！
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <map>#include <cmath>#include <cstring>#include <string>#include <queue>#include <stack>#include <cctype>#include <set>#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())typedef long long LL;using namespace std;int graph[30][30];int c[30];int topo[30];int n;int t;struct Value{ int x,y;};bool cmp(Value a,Value b){ return a.x > b.x;}int main(){#ifndef ONLINE_JUDGE freopen("in.in","r",stdin);#endif map<string,int>un; string name[30]; while(cin >> n && n){ for(int i = 1;i <= n;i++){ cin >> name[i]; un[ name[i] ] = i; } memset(graph,0,sizeof(graph)); for(int i = 1;i <= n-1;i++){ string str1; int num,a,b; cin >> str1; a = un[str1]; cin >> str1 >> num >> str1; b = un[str1]; graph[a][b] = num; graph[b][a] = -1 *num; //cout <<a << " " << b << endl; } for(int k = 1;k <= n;k++){ for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(i == j || k == i || k == j) continue; if(!graph[i][j] &&graph[i][k] &&graph[k][j]){ if(graph[i][k] > 0 && graph[k][j] > 0){ graph[i][j] = graph[i][k] * graph[k][j]; graph[j][i] = -1 * graph[i][k] * graph[k][j]; } else if(graph[i][k] < 0 && graph[k][j] < 0){ graph[j][i] = graph[i][k] * graph[k][j]; graph[i][j] = -1 * graph[i][k] * graph[k][j]; } else if(graph[i][k] < 0 && graph[k][j] > 0){ if(abs(graph[i][k]) > graph[k][j]){ graph[j][i] = abs(graph[i][k]) / graph[k][j]; graph[i][j] = -1 * graph[j][i]; } else{ graph[i][j] = abs(graph[i][k]) / graph[k][j]; graph[j][i] = -1 * graph[i][j]; } } else{ if(graph[i][k] > abs(graph[k][j])){ graph[i][j] = graph[i][k] / abs(graph[k][j]); graph[j][i] = -1 * graph[i][j]; } else{ graph[j][i] = graph[i][k] / abs(graph[k][j]); graph[i][j] = -1 * graph[j][i]; } } } } } } int mark; for(int i = 1;i <= n;i++){ bool flag = 1;; for(int j = 1;j <= n;j++){ if(graph[i][j] < 0){ flag = 0; break; } } if(flag){ mark = i; break; } } Value a[30]; for(int i = 1;i <= n;i++){ a[i-1].x = graph[mark][i]; a[i-1].y = i; } sort(a,a+n,cmp); cout << 1 << name[ a[n-1].y ]; for(int i = n-2;i > -1;i--){ cout << " = "<< a[i].x << name[ a[i].y ] ; } cout << endl; } return 0;}
Problem K: Yikes -- Bikes!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。