oyjpArt ACM/ICPC算法程序設計空間

恩？

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!

呃 ...

你這句話也很“另含玄機”，哈哈！

嘿嘿，roba大牛現身了哈

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

汗。。。
您謙虛了。。。

@richardxx
呵呵 進復賽了就可以了不 看我們這種初賽就被水掉的菜菜。。

百度rejudge了，第二題全過了

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

不謝

呵呵~~

@Surfing
嘿嘿，謝謝分享

你可以參考《算法藝術與信息學競賽》303-304頁
3.地震--最有比率生成樹 一節的解答
和這個非常類似

就是2分枚舉那個答案，然后將除的表達式的權 轉化成+-*表達式的權，再這個基礎上求目標函數。 如果目標函數 != 0，則枚舉的答案應該向使目標函數更接近0的方向取值，

go函數實際求的就是最大權的hamilton回路。用的是基本的壓縮狀態廣搜。

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

@richardxx
現在用這個“窘”字的人真少
@true
沒看懂啊....享受啥？

呵呵
這個就要自己品味了...
因為 我老婆也要看我博客的 哈哈

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

什么啊 轉的啊

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

那你很有發展前途的說~~

我們是軍網 外網應該不能訪問

哦。。。你過題了沒

哦？

@Calvin Kwok
也祝你成功！

哦？你怎么知道答案啊

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

謝謝啊

那個大牛給我個正確的求圓心的坐標的公式？

的確啊，很強大的數據啊

呃。。
Petr Rating還在漲。。。

@ecnu_zp
你也加油！

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

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

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

bingo!
正是我們人工智能的大作業。。

題目是有這樣的要求的：
要求選定的子集是按照題目給的序來覆蓋。
嘿嘿 如果我沒有理解錯你的意思的話

你參考下源代碼吧，如果還WA，我們QQ說。 :)
#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 ?
你的做法是這樣的嗎

可能頁面太長了吧

hehe 那時候我MS一百道題都不到。。。

呵呵
好玩吧

不記得是從哪里轉的了。。

強調下 alpc55就是蔡蕾
再強調下 是男性
哈哈~~~

...
好玩啊

沒有，我問了staff 說那個不一定準

you are welcome

你的樣例是無解的，沒有線段覆蓋【0，10】的區間。