acm.sgu.ru/problem.php
这道题看上去很唬人：给你一个图和一堆顶点，找一条最短路包含所有的顶点。。其实很水。。。
随便找一个需要包含的点中的一个点，找出这个距这点最短路最远的点，那么那个点必然是这段路的起点或终点(为什么自己体会吧(*^__^*) 嘻嘻)。。所以再从找出的这个点出发Dijstra一下。。再找出最远点。。那么这俩点之间必然有一条最短路包含所有的点！。。所以Dp一下然后重建路径就可以了。。
Code：
www.ideone.com/3DzNn

就是一个无向图找vs到vt的第K长简单路。。
这个实际上直接二分+剪枝就可以了。。关键是题目一模一样的SCOI 2007 的kshort(这个的数据范围反而小晕。。)反而A不掉。。囧啊囧。。。。
二分K短路的长度，然后dfs判断是否存在K条小于这个长度的路径，这样就可以知道K长路的长度，然后生成所有这些路，排个序就可以了晕。。
Code：
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
#include<cstring>
#define pb push_back
using namespace std;
const int maxn=100,inf=~0U>>2;
int n,m,k,vs,vt;
struct Edge
{
    int t,c;
    Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
    E[s].pb(Edge(t,c));
    E[t].pb(Edge(s,c));
}
int Dist[maxn];
void Spfa(int vs,vector<Edge> E[maxn])
{
    bool inq[maxn]={0};queue<int> Q;
    for(int i=0;i<n;i++) Dist[i]=inf;
    Dist[vs]=0;inq[vs]=true;Q.push(vs);
    while(Q.size())
    {
        int t=Q.front();Q.pop();inq[t]=false;
        int cost=Dist[t],ncost;
        for(eit e=E[t].begin();e!=E[t].end();++e)
            if((ncost=cost+e->c)<Dist[e->t])
            { Dist[e->t]=ncost;
                if(!inq[e->t])
                    inq[e->t]=true,Q.push(e->t);
            }
    }
}
bool vis[maxn]={0};
int Limit,Num;
void dfs(int no,int gone)
{
    vis[no]=true;
    if(Num>=k)goto end;
    if(gone+Dist[no]>Limit) goto end;
    if(no==vt){Num++;goto end;}
    for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
    {
        dfs(e->t,gone+e->c);
        if(Num>=k) goto end;
    }
    end:
    vis[no]=false;
}
int Now[maxn];
struct Route
{
    int*A;
    int n,Len;
    Route(int _n,int _Len)
    {
        n=_n;Len=_Len;
        A=new int[n];
        memcpy(A,Now,sizeof(int)*n);
    }
    bool operator<(const Route&o)const
    {
        return Len<o.Len;
    }
    void show()const
    {
        cout<<Len<<" "<<n<<endl;
        for(int i=0;i<n-1;i++)
            cout<<A[i]+1<<" ";
        cout<<A[n-1]+1<<endl;
    }
};
vector<Route> Rs;
void Sdfs(int no,int gone,int d)
{
    vis[no]=true;
    Now[d-1]=no;
    if(gone+Dist[no]>Limit) goto end;
    if(no==vt)
    {
        Rs.pb(Route(d,gone));
        goto end;
    }
    for(eit e=E[no].begin();e!=E[no].end();++e)if(!vis[e->t])
    {
        Sdfs(e->t,gone+e->c,d+1);
    }
    end:
    vis[no]=false;
}
bool Check(int _Limit)
{
    Num=0;
    Limit=_Limit;
    dfs(vs,0);
    return Num>=k;
}
void Get(int _Limit)
{
    Limit=_Limit;
    Sdfs(vs,0,1);
    sort(Rs.begin(),Rs.end());
    Rs[k-1].show();
}
void Init()
{
    cin>>n>>m>>k;
    int s,t,c;
    while(m–)
    {
        cin>>s>>t>>c;s–;t–;
        AddEdge(s,t,c);
    }
    cin>>vs>>vt;vs–;vt–;
}
void Work()
{
    Spfa(vt,E);
    int l=0,r=inf;
    if(!Check(r))
    {
        cout<<"No"<<endl;
        return;
    }
    while(l+1<r)
    {
        int m=l+r>>1;
        if(Check(m))
            r=m;
        else
            l=m;
    }
    Get(r);
}
int main()
{
    //freopen("in","r",stdin);
    Init();
    Work();
}

[BeijingWc2008]雷涛的小猫

Time Limit:50000MS Memory Limit:165536K
Total Submit:22 Accepted:15
Case Time Limit:10000MS

Description

Input

Output

Sample Input

Sample Output

Hint

Source
这题算是水题了。。从低到高转移，并且记录每行的最大值，就可以了囧。。
Code：

#include<cstdio>#include<iostream>using namespace std;const int maxn=2000+10;int n,h,d;int N[maxn][maxn]={0};void Init(){ scanf("%d %d %d",&n,&h,&d); for(int i=0;i<n;i++) { int s,x;scanf("%d",&s); while(s–)scanf("%d",&x),N[i][x]++; }}int Best[maxn]={0};int Dp[maxn]={0};void Work(){ for(int i=1;i<=h;i++) for(int j=0;j<n;j++) { if(i-d>=0)Dp[j]>?=Best[i-d]; Dp[j]+=N[j][i]; Best[i]>?=Dp[j]; } printf("%dn",Best[h]);}int main(){ //freopen("in","r",stdin); Init(); Work();}8

[HNOI2007]神奇游乐园

Time Limit:10000MS Memory Limit:165536K
Total Submit:60 Accepted:28
Case Time Limit:1000MS

Description

经历了一段艰辛的旅程后，主人公小P乘坐飞艇返回。在返回的途中，小P发现在漫无边际的沙漠中，有一块狭长的绿地特别显眼。往下仔细一看，才发现这是一个游乐场，专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为n×m的区域，且这个n×m的区域被分成n×m个小格子，每个小格子中就有一个娱乐项目。然而，小P并不喜欢其中的所有娱乐项目，于是，他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目，值越大表示越喜欢。为负时表示他不喜欢，这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中，然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径，从飞艇所在格出发，最后又回到这个格子。小P有一个习惯，从不喜欢浪费时间。因此，他希望经过每个格子都是有意义的：他到一个地方后，就一定要感受以下那里的惊险和刺激，不管自己是不是喜欢那里的娱乐项目。而且，除了飞艇所在格，其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。
在满足这些条件的情况下，小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗？

Input

输入文件中的第一行为两个正整数n和m，表示游乐场的大小为n×m。因为这个娱乐场很狭窄，所以n和m满足：2<=n<=100，2<=m<=6。
接下来的n行，每行有m个整数，第i行第j列表示游乐场的第i行第j列的小格子中的娱乐项目的满意度，这个满意度的范围是[-1000，1000]。同一行的两个整数之间用空格隔开。

Output

输出文件中仅一行为一个整数，表示最高的满意度之和。

Sample Input

Sample Output

Hint

大家测下这个数据
5 5
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
1 1 -100 3 3
结果是30?

Source
饿。。跟Formual 1差不多。。直接上连通性状态压缩Dp就可以了。还要考虑不选当前格子的情况(*^__^*) 嘻嘻……。。

Code还是只能放在ideone上。。。哎。。开始钻研这种Dp了。。这玩意真是NB啊囧。。
http://www.ideone.com/Oh0E1

40004 4100 300 -400 400-100 1000 1000 1000-100 -100 -100 -100-100 -100 -100 1000

这道题目算法就不说了。。关键是我这个实现方法还是很有意思的。。
我直接用一个类来表示状态。。大大简化了代码(*^__^*) 。。
const int maxn=20;
typedef unsigned long long ull;
int n,m;
struct State
{
    ull s;
    State(ull _s=0):s(_s){}
    int get(int i){return s>>(3*i)&7;}
    int operator[](int i){return get(i);}
    void set(int i,int x){s&=~(7ULL<<(3*i));s|=ull(x)<<(3*i);}
    bool operator<(const State&o)const
    {return s<o.s;}
    void normal()
    {
        static int tmp[10],cnt;
        memset(tmp,0,sizeof(tmp));
        cnt=0;
        for(int i=0;i<=m;i++)
        {
            int t=get(i);
            if(!t)continue;
            if(!tmp[t]) tmp[t]=++cnt;
            set(i,tmp[t]);
        }
    }
    void Merge(int a,int b)
    {
        for(int i=0;i<=m;i++)
            if(get(i)==b)
                set(i,a);
        normal();
    }
    bool LegalAsEnd()const
    {
        return s==0;
    }
    void NextRow()
    {
        s<<=3;
    }
    void Show()
    {
        for(int i=0;i<=m;i++)
            cout<<get(i)<<" ";
        cout<<endl;
    }
};
完整的代码在ideone上。。百度放不下囧。。。
http://www.ideone.com/0mrgG

我很无聊的钻研了vector的实现代码，发现这个玩意非常NB，但在很多情况下没有必要减小表的大小，那么vector的速度就成问题了。。
我自己写了个Vector类，只支持加一个元素这个操作，不过速度比vector快了很多囧。。
比如说边表之类的就可以加速了。。
Code：
#include <cstring>
#include <iostream>
#include <ctime>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1;
using namespace std;
template<class T>
struct Vector
{
typedef T* it;
it Mem,End,MemEnd;
void Grow()
{
int s=MemEnd-Mem;
it NewMem=new T[s*2];
memcpy(NewMem,Mem,sizeof(T)*s);
delete[] Mem;Mem=NewMem;
MemEnd=Mem+s*2;
End=Mem+s;
}
Vector()
{
Mem=new T[1];
MemEnd=Mem+1;
End=Mem;
}
void Add(const T&a)
{
if(End==MemEnd)Grow();
*(End++)=a;
}
it begin(){return Mem;}
it end(){return End;}
};
int main()
{
int time=clock();
Vector<int> V;
rep(i,10000000) V.Add(i);
cout<<clock()-time<<endl;time=clock();
vector<int> A;
rep(i,10000000) A.push_back(i);
cout<<clock()-time<<endl;time=clock();
}

[SCOI2009]生日快乐

Time Limit:1000MS  Memory Limit:165536K
Total Submit:50 Accepted:41

Description

windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。
现在包括windy，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。
windy主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。
这样，要切成 N 块蛋糕，windy必须切 N-1 次。
为了使得每块蛋糕看起来漂亮，我们要求 N 块蛋糕的长边与短边的比值的最大值最小。
你能帮助windy求出这个比值么？

Input

包含三个整数，X Y N。

Output

包含一个浮点数，保留6位小数。

Sample Input

5 5 5

Sample Output

1.800000

Hint

【数据规模和约定】
100%的数据，满足 1 <= X,Y <= 10000 ； 1 <= N <= 10 。

Source

Day1

晕。。实际上是水题啊。。直接搜索就可以了囧。。以前我还以为是神牛题晕。。
天啊。。后天就要数学竞赛了我居然在拼命搞OI囧。。。
Code：

#include <algorithm>
#include <cstdio>
using namespace std;
double dfs(double x,double y,int c)
{
if(x>y)swap(x,y);
if(c==1)return y/x;double ret=1e20,r=1.0/c;
for(int i=1;i<c;i++)
ret<?=max(dfs(x*r*i,y,i),dfs(x-x*r*i,y,c-i)),
ret<?=max(dfs(x,y*r*i,i),dfs(x,y-y*r*i,c-i));
return ret;
}
int main()
{
double x,y;int n;
scanf("%lf %lf %d",&x,&y,&n);
printf("%0.6fn",dfs(x,y,n));
}

[Usaco2006 Dec]Milk Patterns

Time Limit:5000MS  Memory Limit:65536K
Total Submit:9 Accepted:6
Case Time Limit:1000MS

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天
产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。
John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的
牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。
比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

4

Source

Gold

直接上Hash。。二分判断就可以了。。代码0.7K囧。。
Code：

#include <algorithm>
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int seed=1333331,maxn=20000;
using namespace std;
typedef unsigned long long ull;
ull P[maxn];
int n,k,A[maxn];
bool Check(int L)
{
ull ret=0;map<ull,int> M;
rep(i,L) ret*=seed,ret+=A[i];
M[ret]=1;
rep(i,n-L)
{
ret-=P[L-1]*A[i];ret*=seed;ret+=A[i+L];
int&x=M[ret];if(++x>=k)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);rep(i,n)scanf("%d",A+i);
P[0]=1;rep(i,n-1)P[i+1]=P[i]*seed;
int l=0,r=n/k+1;
while(l+1<r)
{
int m=(l+r)/2;
if(Check(m)) l=m;
else r=m;
}
printf("%dn",l);
}

在TopCoder上做题目。不会用Marco是不行的，神通广大的Marco能让你的AC时间减少一半甚至以上囧。。这次我潜心研究了TopCoder上各个神牛的Marco，做了个整理。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
#define MP make_pair
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
template<class T> string tostr(T a)
{
OSS out;out<<a;return out.str();
}
int main()
{
int t=100;
long long T[2];
cout<<tostr(t)<<endl;
FILL(T,-1);
cout<<T[1]<<endl;
}

[Usaco2009 Feb]Revamping Trails

Time Limit:10000MS  Memory Limit:65536K
Total Submit:43 Accepted:13
Case Time Limit:1000MS

Description

每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向
泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N).
John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i
走到P１_i

他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，
将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

Input

* 第一行: 三个空格分开的数: N, M, 和 K

* 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

Output

* 第一行: 更新最多Ｋ条路经后的最短路经长度．

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

1

Hint

K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时
为１单位.
N<=10000

Source

Gold
这个很明显是分层图的最短路，不过我的做法有点诡异。就是对每一层用dijstra算出最短路之后再更新下一层。那样空间消耗很低而且速度比标程快一倍晕。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=10000+10;
typedef long long ll;
const ll inf=ll(1)<<60;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c){E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));}
int n,m,k;
ll Dp[2][maxn];
struct State
{
int p;ll c;
State(int _p,ll _c):p(_p),c(_c){}
bool operator<(const State&o)const
{return c>o.c;}
};
priority_queue<State> Q;
int main()
{
cin>>n>>m>>k;int s,t,c;
rep(i,m)scanf("%d %d %d",&s,&t,&c),InsEdge(s-1,t-1,c);
int now=0,next=1;rep(i,n)Dp[next][i]=inf;Dp[next][0]=0;
rep(o,k+1)
{
swap(now,next);
rep(i,n)if(Dp[now][i]!=inf) Q.push(State(i,Dp[now][i]));
//Update now
while(Q.size())
{
State t=Q.top();Q.pop();if(Dp[now][t.p]!=t.c)continue;
Dp[now][t.p]=t.c;int ncost;
for(eit e=E[t.p].begin();e!=E[t.p].end();++e)
if((ncost=t.c+e->c)<Dp[now][e->t])
Dp[now][e->t]=ncost,Q.push(State(e->t,ncost));
}
//Update next
rep(i,n) Dp[next][i]=Dp[now][i];
rep(i,n) for(eit e=E[i].begin();e!=E[i].end();e++)
Dp[next][e->t]<?=Dp[now][i];
}
cout<<Dp[now][n-1]<<endl;
}