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】的区间。