题意:哥伦布找土著换东西,共有四个方案:1 拿钱换等价的东西,(无用条件)2 拿一颗玻璃球代替一枚金币,然后换等价的东西。3 等价的东西可以互换(容易落下这个条件)。4 用东西+钱 换另一样东西(不是补差价),比如 price[1] = 5, price [2] = 20, 但是可以用 thing1 + 5换得thing2 = =。
从上面第四点很明显看出是一个潜在的松弛过程。那么建图的时候就建一个超源S = 0, 货物的价钱即到S的距离。然后跑一发spfa即可。
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; const int N = 50; const int inf = 1 << 28; struct node{ int to, nxt, w; }e[N*N]; int head[N]; int dis[N]; int vis[N]; int cnt; int val[N]; void add(int u, int v, int w) { e[cnt].to = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt++; } void init() { cnt = 0; memset(head, -1, sizeof(head)); memset(val, 0, sizeof(val)); } int n, m; void spfa() { queue<int> q; while( !q.empty() ) q.pop(); memset(vis, 0, sizeof(vis)); for( int i = 1; i <= n; i++ ) dis[i] = inf; vis[0] = 1; dis[0] = 0; q.push(0); while( !q.empty() ) { int now = q.front(); vis[now] = 0; q.pop(); for( int i = head[now]; ~i; i = e[i].nxt ) { int to = e[i].to; //printf("now:%d to: %d\n", now, to); //printf("%d %d %d\n", dis[to], dis[now], e[i].w); if( dis[to] > dis[now] + e[i].w ) { dis[to] = dis[now] + e[i].w; if (!vis[to]) { q.push(to); vis[to] = 1; } } } } } int main() { int tot; for( scanf("%d", &tot); tot--; ) { scanf("%d", &n); init(); int u = 0, v, w; for( int i = 1; i <= n; i++ ) { scanf("%d%d", &v, &w); val[v] = w; add(u, v, val[v]-1); } scanf("%d", &m); while(m--) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ) if( i != j && val[i] == val[j] ) add(i, j, 0); spfa(); for( int i = 1; i <= n; i++ ) printf("%d %d\n", i, dis[i]); memset(vis, 0, sizeof(vis)); int ans = 0; for( int k = 1; k <= n; k++ ) { for( int i = 1; i <= n; i++ ) { for( int j = 1; j <= n; j++ ) { if( i == k || i == j || j == k || vis[k] ) continue; if( dis[k] == dis[i] + dis[j] ) { vis[k] = 1; ans++; } } } } printf("%d\n", ans); } return 0; }
题面长的要死,区域赛还是有唬人的题╮(╯▽╰)╭