oyjpArt ACM/ICPC算法程序设计空间

下面我用n代表点 m代表边
邻接表：访问任任两点之间的边最坏o(n) 遍历一个点的所有边o(该点的度数）
邻接矩阵：访问任两点之间的边o(1) 但是遍历一个点的所有边o(n)
由此可以看出 选择是有目的的
第一 对于稀疏图 有时候内存不够用 不得不待用邻接表
第二 对于比较密集的图 邻接表无甚优势
第三 如果不需要在稀疏图中经常性的遍历一个点的所有边 邻接矩阵是仍首选的

看到你的输入数据似乎用邻接矩阵比较好

一点修改 if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue; 中的 12->15

lz是不是写的麻烦了点
#include <stdio.h>
#include <string.h>
#include <math.h>

const int N = 17;

int main() {
int i, a, b, c, d, x, best = -10000, rec = -1, nc, need, np, hun[N], la[N], su[N], dan[N], p[N], sum[4];
char name[N][100];
scanf("%d %d %d", &nc, &need, &np);
for(i = 0; i < nc; i++) {
scanf("%s %d %d %d", &name[i], &p[i], &hun[i], &la[i]);
su[i] = 1-hun[i]; dan[i] = 1-la[i];
}
scanf("%d %d %d %d", &a, &b, &c, &d);
for(x = 0; x < (1<<nc); ++x) {
memset(sum, 0, sizeof(sum));
int price = 0, cnt = 0;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
cnt++; price += p[i];
}

if(cnt != need || abs(price - np * 12) >= abs(best - np * 12)) continue;
for(i = 0; i < nc; ++i)
if( (x & (1<<i)) != 0) {
sum[0] += hun[i]; sum[1] += su[i];
sum[2] += la[i]; sum[3] += dan[i];
}

if(sum[0] == a && sum[1] == b && sum[2] == c && sum[3] == d) {
best = price; rec = x;
}
}
for(i = 0; i < nc; i++)
if( (rec & (1<<i)) != 0)
puts(name[i]);
printf("%.2lf\n", 0.8* best / np);
return 0;
}

# 致：byron
也祝你好运
希望有机会来北京看你

这么巧啊 同bless

有一些很好的随机算法

呵呵 就聊上了啊 :)

Mod4 余数为0的路径总数问题
已知1..n n个点 以及各个点之间的边以及权 定义路径 从1...n并且边权之和对4取模为0 求这样的路径的个数
Mod4 余数为0的最短路径问题
已知1..n n个点 以及各个点之间的边以及权 定义路径 从1...n并且边权之和对4取模 求这样的路径中路径之和最小的路径

我用了__int64啊

你做的很好了 是我没有做好 慌张了

首先 我们相当于做一个简单测试（判线段相交的快速排斥实验的那种味道）我们把所有节点的入度和出度分别相加 如果入度和和出度和不相等 显然不满足图的要求（因为任意一条边必然产生一个入度和一个出度）。否则我们定义M = SUM(in-degree); 接下来的任务是对这M条边作点的分配。 如果考虑网络流的做法，由于每个点对应着2个权值 in-degree, out-degree，一种常规的做法是将一个点A分成2个点 我们称为A-in & A-out。然后我们建立一个source连接到所有的A-out点 再建立一个sink连接所有的A-in。这样我们就可以成功的把indegree和outdegree作为各自的容量。也就是从source到A-out的capacity定为A的out-degree，A-in到sink的capacity定为A的in-degree。为什么要这样建图呢？实际上作为任何一个可能存在的边 在我们的点一分为2之后 都应该是从A-out到B-in的这样一条边 所以我们这样建图之后 就可以对任一点的out到任一点的in连上一条capacity为1的边（无重边的题目描述）然后run一次最大流 如果能够正确得到M的最大流（实际上就会得到M条边） 这样就满足了题目要求了　呵呵　从整个过程来看　这个和二分图匹配是很像的　实际上　很多题目的网络流建图方案都与２分图匹配有着关联　^_^

@ares_tc_j:
按你的口气是看不起做程序设计竞赛的人了
我来说说程序设计竞赛：
1.程序设计竞赛在于锻炼“脑力”，在熟练掌握各种算法和数据结构 常见数学模型与方法 解决问题的思维与稳健，往往是只一身早早投入项目中的人最最缺乏 也难以得到的珍贵品质 往往是突破一般型人才的关键要素
2.参与程序设计竞赛并非抛开项目 相信很多大学的老师在给项目安排本科生的时候首选的就是代码能力相对稳健的ACM选手 也就是说做程序设计竞赛的人非但不会抛开项目的实践 而是会在合适的时机全身心的投入进去
楼主写了一个a+b的程序你看了就鄙视
自己写了多么了不起的东西啊 空拿室友多么多么怎么怎么管什么用
殊不知 越是不得其真的人越是喜好随口开河

“就你做的这几题，真的没什么可称道的，所以不要沾沾自喜。”
你就找楼主博客里面的题目试试 看看自己能做几道？博大精神的图论算法体系 变幻无穷的计算几何 300行的宽搜 优美的动态规划 人工智能的应用 你又了解多少？

“你说做项目？什么是项目？我怀疑呢，因为你现在的水平...........
好好努力吧，不要被别人蒙蔽眼睛。”
我想问问什么叫蒙蔽 你自己醒醒吧

72 if (dist[v] > dist[u] + w)
73 {
74 now.k = dist[u] + w;
75 now.no = v;
76 push(now);
77 dist[v] = dist[u] + w;
78 }
从这段代码中可以看到 在一次添加节点后 并没有按照常理对其他连接的可改进节点做修正（实际上是模版没有扩充修改一个节点的值然后维护堆性质的功能） 我们把那些旧的节点称为废节点的话 所以在选出dist最小的节点的时候要看看是不是废节点 如果是的就要不断POP出来
while (hs > 0 && h[ 1 ].k > dist[h[ 1 ].no]) pop();
应该很好理解了

谢谢提醒 呵呵

题目我是边做边找的

很多不懂和不熟悉了的东西要补

可能我自己点击了200次？

@zzningxp
sorry 我会的

晕倒 我是菜菜。。。

呵呵 各位大牛们见笑了~。。。

o 对 呵呵~~ 我改一下
:)

抱歉 我说的不是很清楚

首先 我这里的p[]数组代表的时parent 也就是在树形的并查集中父结点的标号 比如 如果1节点（根）的子节点是2，3 则p[2] = p[3] = 1; 而根节点的父结点将会被初始化为自己的标号 如p[1] = 1;
在树形的并查集中 我们将根节点定义为这个集合的代表元
而在这个题目中我们将代表元定义为这个从某一天往上数第一个空闲的日期 比如 日期
1 2 3 4 5 6 7 8 9 10
如果3是空闲（没有被分配一个商品）而4，5都已经分配 那么p[4]=p[5] = 3;
如果4也是空闲 那么p[3] = 3; p[4] = 4;
这样 我们在分配商品的时候 要得到从某一天往上数第一个空闲的日期 就是直接查找这一天所在集合里面的代表元就可以了
从另外一个角度上来看 这个集合其实时一个空闲的天 后面跟着一连串的非空闲天
比如
1 2 3 4 5 6 7 8 9 10
如果3是空闲（没有被分配一个商品）而4，5都已经分配 6没有分配 那这个集合就是3，4，5 其中代表元为3
以下面这段代码来作说明吧
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]没用用过 那么p[d-1]就应该=d-1
}
如果flag[g[i].d] is true 代表g[i].d这一天已经被分配 于是空闲的天就是find_set(g[i].d);
否则 d = g[i].d; 就是这一天 这个时候集合只有一个元素 就是自己作为代表元
if(d > 0) cnt += g[i].p; 因为有可能代表元为0（设置数据的时候p[d-1]为了不越界 故意留出0） 实际上代表没有空闲 比如1，2，3，4都满了 你要放在3的地方 就会得到0 这个位置 所以要>0才能cnt += g[i].p;
flag[d] = 1; 接着把刚才找到的空闲处标记
p[d] = p[d-1]; 然后把刚才找到的空闲处的代表元设置一下
这里的设置对于下面2中情况都是对的
情况1： 1 2 3 4 5
2空闲 3空闲 我在3处放 然后标记p[3] = p[2] = 2;
情况2： 1 2 3 4 5 6
2满 3满 4空闲 我在4处放 然后标记 p[4] = p[3] = 1
基本上就是这样了 没有解释清楚 真不好意思 :)

p[d]代表选中在D之前第一个空闲的日子
就是说d这个日期用了之后 那么第一个空闲的日子就一定时p[d-1];
也可以这样写：
for(i = 0; i<ng; i++) {
int d = g[i].d;
if(flag[g[i].d]) d = find_set(g[i].d);
if(d > 0) cnt += g[i].p;
flag[d] = 1;
p[d] = p[d-1]; //如果p[d-1]没用用过 那么p[d-1]就应该=d-1
}

[quote] "You can assume that each player has made at least two moves, ..."
which means that there must be 4 moves at the beginning :)

太猛了！

6级出来了 比4级低10分。。。呵呵

没必要写病毒的说 有什么很大意义么

为什么你可以写网站，而我现在要一天到晚写这个BT题目啊……
55555555555555555555555555555……………………

Peking University
Here we imply Peking University ACM Online Judge

呵呵 看了Butterfly Effect 1&2 就是这种感觉~~ 哈哈 没事啦

of course not

娃哈哈哈 呵呵 豪兄猛阿~~~

呵呵。我K题的速度还真是慢。哈哈