1. java.. java.. java…最近老听到java,也不知道什么时候开始Java变成了万能的语言. 一旦程序错了，瞬间就怀疑是不
是精度问题导致自己算法错了，从不怀疑自己那脆弱的算法有没有问题，能不能改进。 ACM都快2年了，就没见过一道题目非Java不行的。 当没勇气承认自己无力的算法的时候，请大家不要埋怨一直陪伴着你的语言. 人就是这样一走进误区，就会茫然不知，乱闯乱撞,就快死在那里了也不知道。 人还很奇怪，相同的场景，相同的陷阱，还是会一次次往里跳, 还跳的还很开心…..
2. 贼牛叉的算法老挂在嘴边, 碰到有点想法的题目就埋怨算法不会。更讽刺的是当大批新手队秒掉了之后，还在那里恍惚奇怪他们什么时候也学那XX算法了…… 人额~总是贪婪的想在最短的时间学会所有的算法，然后静静的死在那些“自以为学会的算法”面前，还很安详的那种….
3. 最近老碰到代码技巧很高的统计题，很难敲出，而且敲出了也很难AC。如果自己都对自己没自信，敢问你上去敲个屁
啊….傻里傻气的敲个2到3小时。。然后很光彩的和队友说”那个题目数据真变态,一开始就知道会过不了得”….. 典型就一
个悲剧，为你的队友感到伤心。自知自明和自信是同等重要的。
4 ACM.. ACM… 为什么叫ACM呢？.. 因为是三个字母，所以一个队才有三个人， 为什么是ACM呢？ 正因为三个人在一起才会
AC many 题目。 不能做到三人合作，就请解散吧….
5. 比赛5小时，有些队从开始到结束都忙碌，有些很茫然，还有那么一些则很搞笑。 搞笑到看见自己的提交WA了还会自
笑…..然后哼着歌乱搞一气等待比赛结束…
6。 队友不是神话，有些东西不讲明白是很痛苦的。
.
.
.
.
.
.
最近在ACM方面见到不光彩面比较多，有好多也是自己或队友的自嘲。可能是有点极端，但我希望带讽刺的手笔自我批评一番
。ACM时日不多。。 我希望不久以后写退役总结时不是这个语调….
生活瞬间 yifenfei
伴随着浙大月赛的纠结，大学间最后的暑假也走到了尽头……
有很多想做的事情，但可惜大半都没能在这个夏天完成, 可能是少那么一点决心，也可能是缺那么一点机会~~最终还是把整
个暑假献给了ACM，虽然在那片熟悉的领域少了去年同个时候的那份激情，但自我感觉2个月以来的每一步，自己走的还是蛮踏实的
。
暑假刚开始那扑朔迷离的组队，最终走了陈晟，来了胡浩，虽然有点舍不得陈晟，1年来和我，和天涯的配合还是相当默契的
，但是不可否认胡浩的到来给我们队带来了冲劲，不知不觉中让我感觉，我们仿佛也有机会去冲击下那遥远的梦想。
26场积分赛中，17场内部第一，还有最后那一场联合训练赛戏剧性的捧杯算是对重组后我们的肯定。现在好好总结下整个暑假
，发现其实过的还蛮开心的，和那群熟悉的人，去了好几次川味馆，吃了好几回堡(好像还在该过程中见到了朱丹…..), 一起去吃
过海鲜，玩过台球，但没有陪他们去看电影~~因为…..那个~呵呵。 还有集训后半程的那个”多塔再起”，也会成为我2009年夏天
最美回忆中的一部分…..
最后一次全国赛，不知道能走多远，但我会好好珍惜，要对得起那段逝水无痕的光阴。还没想好参加全国赛的队名，另外两个
人也都没提起过，到时候可能是件蛮难以决定的事情。
接着剩下来的就只有那可怜的一年，这辈子学生时代的最后一年了，除了考虑下毕业后的事情，我还很想尝试一下很多新鲜的
东西，做一些未曾做过的事情。比如最近得知有位朋友很想得到一台时光机，回到过去，所以晚上睡觉的时候老在想做时光机要什
么材料……做时光机应该是一件蛮帅的事情，要尝试一下~~呵呵。
集训队一大半都提着行李开心回家休息去了，发现自己真的很懒，明知道有可能十一不能回去，但还是懒的乘火车回家，常常
找借口安慰自己“时间啊~~~那个很快的，过年一杂眼而已…..”
也不知道为什么，这2天都起的有点早，今天的下沙天气爽的出奇，过滤掉了浮躁的那一层，整个思维都灵动了很多，但仿佛
也提醒着我这个夏天时真的过去了…….
生活瞬间 yifenfei，暑假
SGU 185 Two shortest
最近一直在重温网络流方面的方面的知识，总感觉这方面比较散，昨天重新整理了下最小费流模板，今天又重新理了便Dinic，对分层的感念虽然还没有以前那么深刻了，但体会却有所不同。
SGU 185 蛮经典的题目，贴下代码，记录下学习的过程
- #include<iostream>
- using namespace std;
-
- #define maxn 500
- #define inf 1<<28
- struct edge{
- int v, next;
- int val;
- } net[ maxn * maxn ];
- int level[maxn], next[maxn], Qu[maxn], out[maxn];
-
- class Dinic {
- public:
- int end;
- Dinic() {
- end = 0;
- memset( next, -1, sizeof(next) );
- }
- inline void insert( int x, int y, int c) {
- net[end].v = y, net[end].val = c, net[end].next = next[x], next[x] = end ++;
- net[end].v = x, net[end].val = 0, net[end].next = next[y], next[y] = end ++;
- }
- bool BFS( int S, int E ) {
- memset( level, -1, sizeof(level) );
- int low = 0, high = 1;
- Qu[0] = S, level[S] = 0;
- for( ; low < high; ) {
- int x = Qu[low];
- for( int i = next[x]; i != -1; i = net[i].next ) {
- if( net[i].val == 0 ) continue;
- int y = net[i].v;
- if( level[y] == -1 ) {
- level[y] = level[x] + 1;
- Qu[ high ++] = y;
- }
- }
- low ++;
- }
- return level[E] != -1;
- }
-
- int MaxFlow( int S, int E ){
- int maxflow = 0;
- for( ; BFS(S, E) ; ) {
- memcpy( out, next, sizeof(out) );
- int now = -1;
- for( ;; ) {
- if( now < 0 ) {
- int cur = out[S];
- for(; cur != -1 ; cur = net[cur].next )
- if( net[cur].val && out[net[cur].v] != -1 && level[net[cur].v] == 1 )
- break;
- if( cur >= 0 ) Qu[ ++now ] = cur, out[S] = net[cur].next;
- else break;
- }
- int u = net[ Qu[now] ].v;
- if( u == E ) {
- int flow = inf;
- int index = -1;
- for( int i = 0; i <= now; i ++ ) {
- if( flow > net[ Qu[i] ].val )
- flow = net[ Qu[i] ].val, index = i;
- }
- maxflow += flow;
- for( int i = 0; i <= now; i ++ )
- net[Qu[i]].val -= flow, net[Qu[i]^1].val += flow;
- for( int i = 0; i <= now; i ++ ) {
- if( net[ Qu[i] ].val == 0 ) {
- now = index - 1;
- break;
- }
- }
- }
- else{
- int cur = out[u];
- for(; cur != -1; cur = net[cur].next )
- if (net[cur].val && out[net[cur].v] != -1 && level[u] + 1 == level[net[cur].v])
- break;
- if( cur != -1 )
- Qu[++ now] = cur, out[u] = net[cur].next;
- else out[u] = -1, now --;
- }
- }
- }
- return maxflow;
- }
- };
-
-
-
- int cost[maxn][maxn], d[maxn], hash[maxn];
- int n, m;
-
- void Dijkstra() {
- for( int i = 1; i <= n; i ++ ) d[i] = inf;
- memset( hash, 0, sizeof(hash));
- d[1] = 0, hash[1] = 1;
- int x = 1;
- int now = 0;
- while( 1 ) {
- for( int i = 1; i <= n; i ++ )
- if( !hash[i] && now + cost[x][i] < d[i])
- d[i] = now + cost[x][i];
- now = inf;
- for( int i = 1; i <= n; i ++ )
- if( !hash[i] && d[i] < now )
- now = d[i], x = i;
- if( now == inf ) break;
- hash[x] = 1;
- }
- }
-
- int DFS( int x ) {
- if( x == n ) {
- printf("%d\n", n);
- return 1;
- }
- printf("%d ", x);
- for( int i = next[x]; i != -1; i = net[i].next ) {
- if( !(i&1) && net[i].val == 0 ) {
- net[i].val = -1;
- if( DFS( net[i].v ) )
- return 1;
- }
- }
- return 0;
- }
- int main() {
- while( scanf("%d %d",&n,&m) != EOF ) {
- for( int i = 1; i <= n; i ++ ) for( int j = 1; j <= n; j ++ )
- cost[i][j] = inf;
- while( m -- ){
- int x, y, val;
- scanf("%d %d %d",&x,&y,&val);
- cost[x][y] = cost[y][x] = val;
- }
- Dijkstra();
- Dinic my;
- for( int i = 1; i <= n; i ++ ) {
- for( int j = 1; j <= n; j ++ ) {
- if( i == j ) continue;
- if( d[i] + cost[i][j] == d[j] )
- my.insert( i, j, 1);
- }
- }
- int ans = my.MaxFlow(1, n);
- if( ans < 2 ) {
- printf("No solution\n");
- continue;
- }
- DFS( 1 );
- DFS( 1 );
- }
- return 0;
- }
生活瞬间 网络流
zoj 3404
问巫妖的大招能不能弹死确定的怪物！
比赛的时候想成了拆点的最大流，写完发现弹射K次这个条件不能满足，没做出！
其实对于固定的一点，只能通过它一步可到的点反射过来的，所以最优的方式就是该点于其周围可达的点相互之间反弹。
分类构造最优方案，分如果巫妖第一步就能打到和第一步不能直接打到,如果不能直接弹到，则求个最短距离，使其最快弹到目标。
- #include<iostream>
- #include<queue>
- #include<vector>
- using namespace std;
-
- #define maxn 1010
- vector< int > hd[maxn];
- int n,R,K,D;
- int val[maxn];
- int x[maxn], y[maxn];
- int hash[maxn];
-
- int BFS() {
- queue<int> yifenfei;
- yifenfei.push( 1 );
- memset( hash, -1, sizeof(hash) );
- hash[1] = 0;
- while( !yifenfei.empty() ) {
- int a = yifenfei.front();
- if( a == n ) return hash[n];
- for( int i = 0; i < hd[a].size(); i ++ ) {
- int b = hd[a][i];
- if( hash[b] == -1 ) {
- hash[b] = hash[a] + 1;
- yifenfei.push( b );
- }
- }
- yifenfei.pop();
- }
- return -1;
- }
-
- int main () {
- int T;
- scanf("%d",&T);
- while( T -- ) {
- scanf("%d %d %d %d",&n,&R,&K,&D);
- for( int i = 1; i <= n; i ++ ) {
- scanf("%d %d %d",&x[i],&y[i],&val[i]);
- if( val[i] % D == 0 ) val[i] /= D;
- else val[i] = val[i] / D + 1;
- hd[i].clear();
- }
- val[1] = 0;
- R *= R;
- for( int i = 1; i <= n; i ++ ) {
- for( int j = 1; j <= n; j ++ ) {
- if( i != j && (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) *
- (y[i] - y[j]) <= R )
- hd[i].push_back(j);
- }
- }
- int res = 0;
- for( int i = 0; i < hd[n].size(); i ++ )
- res += val[ hd[n][i] ];
- int cost = BFS();
- if( cost == -1 ) printf("NO\n\n");
- else {
- if( cost == 1 ) {
- int ans = min( (K + 1)/2, res + 1);
- if( ans >= val[n] ) printf("YES\n\n");
- else printf("NO\n\n");
- }
- else {
- K = K - cost + 2;
- int ans = min( K/2, res);
- if( ans >= val[n] ) printf("YES\n\n");
- else printf("NO\n\n");
- }
- }
- }
- return 0;
- }
个人题解 浙大月赛，解题报告，yifenfei
