亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

【BZOJ】1050: [HAOI2006]旅行comf(暴力+并查

系統 1673 0

http://www.lydsy.com/JudgeOnline/problem.php?id=1050

表示被暴力嚇到了orz

我竟然想不到。。。我竟然還想到分數規劃,,但是不可做。。。然后又想到最小生成樹,,然后不會做orz

我一直在糾結怎么最大化(或最小化)分母和最小化(或最大化)分子的做法。。。。。但是。。。。不會orz

沒想到是暴力orz

直接排序后枚舉最小的邊,生成樹后要最大的邊最小(排序后即可orz),然后更新答案即可。

但是不知道之前寫錯了啥wa了兩發,,,隨便改改才過orz

      #include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const int N=1005, M=10005;

struct dat { int x, y, w; }a[M];

inline const bool cmp(const dat &a, const dat &b) { return a.w<b.w; }

int p[N], ans1, ans2, n, m;

const int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }

const int gcd(const int &a, const int &b) { return !b?a:gcd(b, a%b); }



int main() {

	read(n); read(m);

	for1(i, 1, m) read(a[i].x), read(a[i].y), read(a[i].w);

	int s=getint(), t=getint();

	sort(a+1, a+1+m, cmp);

	bool flag=1;

	for1(i, 1, m) {

		for1(j, 1, n) p[j]=j;

		int j=i;

		for(; j<=m; ++j) {

			int fx=ifind(a[j].x), fy=ifind(a[j].y);

			p[fx]=fy;

			if(ifind(s)==ifind(t)) {

				flag=0;

				if(a[j].w*ans2<=a[i].w*ans1) ans1=a[j].w, ans2=a[i].w;

				break;

			}

		}

		if(ifind(s)!=ifind(t)) break;

		if(a[j].w*ans2<=a[i].w*ans1) ans1=a[j].w, ans2=a[i].w;

	}

	if(flag) { puts("IMPOSSIBLE"); return 0; }

	int d=gcd(ans1, ans2);

	ans1/=d; ans2/=d;

	if(ans2==1) printf("%d\n", ans1);

	else printf("%d/%d\n", ans1, ans2);

	return 0;

}


    

?


?

?

Description

給你一個無向圖,N(N<=500)個頂點, M(M<=5000)條邊,每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T,求一條路徑,使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑,輸出”IMPOSSIBLE”,否則輸出這個比值,如果需要,表示成一個既約分數。 備注: 兩個頂點之間可能有多條路徑。

Input

第一行包含兩個正整數,N和M。 下來的M行每行包含三個正整數:x,y和v。表示景點x到景點y之間有一條雙向公路,車輛必須以速度v在該公路上行駛。 最后一行包含兩個正整數s,t,表示想知道從景點s到景點t最大最小速度比最小的路徑。s和t不可能相同。

Output

如果景點s到景點t沒有路徑,輸出“IMPOSSIBLE”。否則輸出一個數,表示最小的速度比。如果需要,輸出一個既約分數。

Sample Input

【樣例輸入1】
4 2
1 2 1
3 4 2
1 4
【樣例輸入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【樣例輸入3】
3 2
1 2 2
2 3 4
1 3

Sample Output

【樣例輸出1】
IMPOSSIBLE
【樣例輸出2】
5/4
【樣例輸出3】
2

HINT

?

【數據范圍】

1< ?N < = 500

1 < = x, y < = N,0 < v < 30000,x ≠ y

0 < M < =5000

?

Source

?

?

【BZOJ】1050: [HAOI2006]旅行comf(暴力+并查集)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 成人国产精品999视频 | 四虎影院wwww | 亚洲一区二区三区精品影院 | 国外欧美一区另类中文字幕 | 亚洲欧洲免费视频 | 欧美a一片xxxx片 | 内衣办公室动漫久久影院 | 亚洲国产成人久久 | 元龙第三季动漫在线观看免费版 | 国产在线视精品麻豆 | 九九99九九在线精品视频 | 久久宗合色 | 日本激情视频一区二区三区 | 国产精品一区伦免视频播放 | 在线高清一级欧美精品 | 日日狠狠久久偷偷四色综合免费 | 久久综合狠狠综合久久 | 精品视频在线视频 | 非洲黑人xxxxxbbbbbb | 亚洲国产字幕 | 婷婷在线视频观看 | 九九九九九九精品免费 | 91资源在线视频 | 精品日韩一区二区 | 99视频精品全国在线观看 | 奇米影视狠狠久久中文 | 色综合久久久久久久久五月性色 | 天天躁狠狠躁狠狠躁夜夜躁 | 97成人免费视频 | www.4虎影院 www.777奇米 | 99国产精品九九视频免费看 | 久热官网 | 午夜在线播放 | 免费一区二区三区免费视频 | 草免费视频 | 四虎成人免费观看在线网址 | 妇女网站爱嘿嘿视频免费观看 | 久久久综合视频 | 日日夜夜天天干 | 美美女高清毛片视频黄的一免费 | 91精品国产91久久久久久青草 |