天天看點
傳回

算法課複習 -- 優先隊列、最短路

POJ #3253 : Fence Repair

傳送門：http://poj.org/problem?id=3253

題意：給n個鋸完後的木頭的長度。每次鋸a+b長度的木頭花費a+b。問原來的一整塊大木頭鋸完最少花費多少。

思路：貪心，Huffman編碼。用優先隊列，每次把最小的兩塊拿出來相加再塞回隊列，隊列裡最後一個元素就是答案。

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9;
const double _e = 10e-6;
const int maxn = 2e4 + 10;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y, z;

int n;

struct cmp
{
	bool operator()(int a, int b)
	{
		return a > b;
	}
};

void solve()
{
	priority_queue<int, vector<int>, cmp> que;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		que.push(x);
	}
	ll ans = 0;
	while (que.size() > 1) {
		int a = que.top(); que.pop();
		int b = que.top(); que.pop();
		que.push(a + b);
		ans += a + b;
	}
	printf("%lld\n", ans);
}

int main()
{
	while (~scanf("%d", &n)) 
		solve();
	return 0;
}

POJ #3259 : Wormholes

傳送門：http://poj.org/problem?id=3259

題意：給出n個點，m條正的無向邊，w條負的有向邊。問有沒有負環。

思路：Bellman-Ford判斷有沒有負環。如果有點在第n次還在更新，那就有負環。

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9;
const double _e = 10e-6;
const int maxn = 510;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y, z;

struct edge
{
	int from, to, cost;
};

int t, n, m, w;
edge e[6010];

bool loop()
{
	int d[maxn]; cl0(d);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m * 2 + w; j++) {
			edge v = e[j];
			if (d[v.to] > d[v.from] + v.cost) {
				d[v.to] = d[v.from] + v.cost;
				if (i == n)
					return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &w);
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%d", &x, &y, &z);
			e[i * 2 - 1] = edge{ x,y,z };
			e[i * 2] = edge{ y,x,z };
		}
		for (int i = m * 2 + 1; i <= m * 2 + w; i++) {
			scanf("%d%d%d", &x, &y, &z);
			e[i] = edge{ x,y,-z };
		}
		if (loop())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

LightOJ #1074 : Extended Traffic

傳送門：http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1074

題意：給出n個路口m條有向邊，每個路口有一個忙碌值。有q個詢問，問從點1到詢問的點最小的花費和，若小于3或無法到達則輸出‘?’。花費為(終點忙碌值-起點忙碌值)^3。

思路：因為是3次方，是以是可能存在負環的。還是用Bellman-Ford求單源最短路+判哪些點在負環裡。

多開一個cycle數組，初始化為0，和算最短路一樣不斷更新，最終所有cycle[i]<0的點i都在負環裡。

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9 + 10;
const double _e = 10e-6;
const int maxn = 210;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y, z;
char c;

struct edge
{
	int from, to, cost;
};

int t, n, m, q;
int cost[maxn], d[maxn], cycle[maxn];
edge e[maxn*maxn];

int cal(int a, int b)
{
	return (b - a)*(b - a)*(b - a);
}

void solve()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			edge v = e[j];
			if (d[v.to] > d[v.from] + v.cost) {
				d[v.to] = d[v.from] + v.cost;
				cycle[v.to] = cycle[v.from] + v.cost;
			}
		}
	}
}

int main()
{
	scanf("%d", &t);
	for (int _ = 1; _ <= t; _++) {	
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			d[i] = INF;
		d[1] = 0; cl0(cycle);
		for (int i = 1; i <= n; i++)
			scanf("%d", &cost[i]);
		scanf("%d", &m);
		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &x, &y);
			e[i] = edge{ x,y,cal(cost[x],cost[y]) };
		}
		solve(); 
		scanf("%d", &q);
		printf("Case %d:\n", _);
		while (q--) {
			scanf("%d", &x);
			if (d[x] < 3 || d[x] == INF || cycle[x] < 0)puts("?");
			else printf("%d\n", d[x]);
		}
	}
	return 0;
}

POJ #1949 : Chores

傳送門：http://poj.org/problem?id=1949

題意：有n件家務活，每個都有完成需要的時間和前置家務。問全部完成最快要多久。

思路：優先隊列，記錄點和結束該任務的時間，按時間從小到大排。記每個點的入度，每當入度為0就進隊列，不斷維護最大值就是答案。

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9 + 10;
const double _e = 10e-6;
const int maxn = 10010;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y, z;
char c;

int n, m, ans;
int cost[maxn], in[maxn];
vector<int> son[maxn];

struct node {
	int id;
	int ans;
};

struct cmp {
	bool operator()(node a, node b) {
		return a.ans > b.ans;
	}
};

void solve()
{
	priority_queue<node, vector<node>, cmp> que;
	for (int i = 1; i <= n; i++)
		if (in[i] == 0)que.push(node{ i,cost[i] });
	while (!que.empty()) {
		node u = que.top(); que.pop();
		ans = max(ans, u.ans);
		for (int i = 0; i < son[u.id].size(); i++) {
			int v = son[u.id][i];
			in[v]--;
			if (in[v] == 0)
				que.push(node{ v, u.ans + cost[v] });
		}
	}
}

int main()
{
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++)
			son[i].clear();
		cl0(in); ans = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &cost[i], &m);
			while (m--) {
				scanf("%d", &x);
				son[x].push_back(i);
				in[i]++;
			}		
		}
		solve();
		printf("%d\n", ans);
	}
	return 0;
}

POJ #1860 : Currency Exchange

傳送門：http://poj.org/problem?id=1860

題意：有n種貨币以及m種交易，給定初始時有的貨币種類（1種）和貨币金額。每種交易都指定2種貨币，以及交易的匯率和手續費。問有沒有可能錢越換越多。

思路：實際上就是判負環。Bellman-Ford判斷即可。

AC代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<utility>
#include<algorithm>
#include<utility>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<map>
#include<ctime>
#include<functional>
#include<bitset>
#define P pair<int,int>
#define ll long long
#define ull unsigned long long
#define lson id*2,l,mid
#define rson id*2+1,mid+1,r
#define ls id*2
#define rs (id*2+1)
#define Mod(a,b) a<b?a:a%b+b
#define cl0(a) memset(a,0,sizeof(a))
#define cl1(a) memset(a,-1,sizeof(a))
using namespace std;

const ll M = 1e9 + 7;
const ll INF = 1e9;
const double _e = 10e-6;
const int maxn = 1e4 + 10;
const int matSize = 9;
const int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
const int _dx[8] = { -1,-1,-1,0,0,1,1,1 }, _dy[8] = { -1,0,1,-1,1,-1,0,1 };

int x, y, z;
char c;

struct edge
{
	int from, to;
	double r, c;
};

int n, m, s;
double ss, a1, a2, a3, a4;
edge e[210];

bool loop()
{
	double d[maxn]; cl0(d); d[s] = ss;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m * 2; j++) {
			edge v = e[j];
			if (d[v.to] < (d[v.from] - v.c)*v.r) {
				d[v.to] = (d[v.from] - v.c)*v.r;
				if (i == n)
					return true;
			}
		}
	}
	return false;
}

int main()
{
	while (~scanf("%d%d%d%lf", &n, &m, &s, &ss)) {
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%lf%lf%lf%lf", &x, &y, &a1, &a2, &a3, &a4);
			e[i * 2 - 1] = edge{ x,y,a1,a2 };
			e[i * 2] = edge{ y,x,a3,a4 };
		}
		if (loop()) puts("YES");
		else puts("NO");
	}	
	return 0;
}
算法課複習 圖論 優先隊列 最短路 負環
上一篇: 算法課複習 -- 圖、Dijkstra
下一篇: 算法課複習 -- 分治

繼續閱讀