oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

恩？

Contact me via POJ mail : alpc12
email(MSN also) : yescrystalblue@sina.com

1724 roads的代碼：
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 101;
struct Node {int x, w, f; void set(int xx, int ww, int ff) {x = xx; w = ww; f = ff;} };
vector<Node> adj[N][N];
int money, nv, ne;

bool operator<(const Node& a, const Node& b) { return a.w > b.w; }

void solve() {
int x, i, j, y;
priority_queue<Node> pq;
Node now, cur;
now.set(0, 0, 0);
pq.push(now);
while(!pq.empty()) {
cur = pq.top();
pq.pop();
x = cur.x;
if(x == nv-1) {
printf("%d\n", cur.w);
return;
}
for(i = 0; i < nv; ++i) {
for(j = 0; j < adj[x][i].size(); j++) if(cur.f + adj[x][i][j].f <= money) {
y = adj[x][i][j].x;
now.set(y, cur.w + adj[x][i][j].w, cur.f + adj[x][i][j].f);
pq.push(now);
}
}
}
printf("-1\n");
}

int main() {
int i, u, v, w, f;
Node now;
scanf("%d %d %d", &money, &nv, &ne);
for(i = 0; i < ne; ++i) {
scanf("%d %d %d %d", &u, &v, &w, &f);
--u; --v;
now.set(v, w, f);
adj[u][v].push_back(now);
}

solve();

return 0;
}

good!

呃 ...

你這句話也很“另含玄機(jī)”，哈哈！

嘿嘿，roba大牛現(xiàn)身了哈

@ 小Young
就是廣搜用的隊(duì)列
不用隊(duì)列你的意思是深搜么？

汗。。。
您謙虛了。。。

@richardxx
呵呵 進(jìn)復(fù)賽了就可以了不 看我們這種初賽就被水掉的菜菜。。

百度rejudge了，第二題全過(guò)了

@w
謝謝 有些事情真的不容易 但是總要學(xué)著去做

不謝

呵呵~~

@Surfing
嘿嘿，謝謝分享

你可以參考《算法藝術(shù)與信息學(xué)競(jìng)賽》303-304頁(yè)
3.地震--最有比率生成樹 一節(jié)的解答
和這個(gè)非常類似

就是2分枚舉那個(gè)答案，然后將除的表達(dá)式的權(quán) 轉(zhuǎn)化成+-*表達(dá)式的權(quán)，再這個(gè)基礎(chǔ)上求目標(biāo)函數(shù)。 如果目標(biāo)函數(shù) != 0，則枚舉的答案應(yīng)該向使目標(biāo)函數(shù)更接近0的方向取值，

go函數(shù)實(shí)際求的就是最大權(quán)的hamilton回路。用的是基本的壓縮狀態(tài)廣搜。

@DenoFiend
呵呵 搞ACM的喜歡自己感慨下子

@richardxx
現(xiàn)在用這個(gè)“窘”字的人真少
@true
沒(méi)看懂啊....享受啥？

呵呵
這個(gè)就要自己品味了...
因?yàn)?我老婆也要看我博客的 哈哈

haha，這都被你猜到了啊，你看你的心理...

什么啊 轉(zhuǎn)的啊

每條邊拆成2條邊 。 然后對(duì)每條邊設(shè)一個(gè)DP值。
比如邊A->B. B連接的其他點(diǎn)的集合叫做S(S中去掉A)
dp[A->B] = Min(Capacity[A->B], 加合(dp[B->Ci]));
可以通過(guò)2次DFS來(lái)求出這些DP值。第一次求出一個(gè)方向的邊的DP值，再一次求出反向。
試著畫個(gè)圖來(lái)理解吧:)

那你很有發(fā)展前途的說(shuō)~~

我們是軍網(wǎng) 外網(wǎng)應(yīng)該不能訪問(wèn)

哦。。。你過(guò)題了沒(méi)

哦？

@Calvin Kwok
也祝你成功！

哦？你怎么知道答案啊

加油，中南賽的集體潰敗，算是給所有人的一個(gè)警鐘吧

謝謝啊

那個(gè)大牛給我個(gè)正確的求圓心的坐標(biāo)的公式？

的確啊，很強(qiáng)大的數(shù)據(jù)啊

呃。。
Petr Rating還在漲。。。

@ecnu_zp
你也加油！

@ haha
這還不夠傻啊。。。哈哈

我真不記得密碼了啊。。。

代碼找不到了。。。
不記得密碼了

bingo!
正是我們?nèi)斯ぶ悄艿拇笞鳂I(yè)。。

題目是有這樣的要求的：
要求選定的子集是按照題目給的序來(lái)覆蓋。
嘿嘿 如果我沒(méi)有理解錯(cuò)你的意思的話

你參考下源代碼吧，如果還WA，我們QQ說(shuō)。 :)
#include <stdio.h>
#include <string.h>

const int N = 1010;
const int T = 2520;
const int MAXINT = 123456789;
int n;
int u[N], d[N];
bool dp[2][N];
int gcd[11][11];

int GCD(int a, int b) {
if(a < b) return GCD(b, a);
while(b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}

inline int LCM(int a, int b) {
return a * b / GCD(a, b);
}

bool ok(int time, int i) {
int t = time % (u[i] + d[i]);
if(t == 0 || t > u[i]) return false;
return true;
}


int main() {
int ntc, i, t, j;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d", &n);
int lcm = 1;
u[0] = u[n+1] = MAXINT; d[0] = d[n+1] = 0;
for(i = 1; i <= n; ++i) {
scanf("%d %d", &u[i], &d[i]);
lcm = LCM(lcm, u[i] + d[i]);
}
n += 2;
memset(dp, false, sizeof(dp));
dp[0][0] = 1;
for(t = 1; t <= lcm; ++t) {
int now = t % 2;
memset(dp[now], false, sizeof(dp[now]));
for(i = 0; i < n; ++i) if(ok(t, i)) {
for(j = i-5; j <= i+5; j++) if(j >= 0 && j < n) {
if(dp[!now][j]) { dp[now][i] = 1; break; }
}
}
if(dp[now][n-1]) { printf("%d\n", t); break; }
}
if(t > lcm) printf("NO\n");
}
return 0;
}

o ?
你的做法是這樣的嗎

可能頁(yè)面太長(zhǎng)了吧

hehe 那時(shí)候我MS一百道題都不到。。。

呵呵
好玩吧

不記得是從哪里轉(zhuǎn)的了。。

強(qiáng)調(diào)下 alpc55就是蔡蕾
再?gòu)?qiáng)調(diào)下 是男性
哈哈~~~

...
好玩啊

沒(méi)有，我問(wèn)了staff 說(shuō)那個(gè)不一定準(zhǔn)

you are welcome

你的樣例是無(wú)解的，沒(méi)有線段覆蓋【0，10】的區(qū)間。