Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024
Main » 2013 » October » 16
[NOIP2012模拟赛No.21]第二短路

O(Km)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define N 200010
#define S 5010
#define L 400010
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
int last[N],pre[N],x[N],y[N],z[N],q[L],V[N];
int e[N],w[N],len,dis1[S],dis2[S],n,r;
void add(int x,int y,int z)
{
  pre[++len]=last[x];
  last[x]=len;
  e[len]=y;w[len]=z;
}
void C(int &x){if (x==L) x=1;}
void SPFA(int v0,int (&dis)[S])
Views: 274 | Added by: dhy0077 | Date: 10.16.2013

[模拟赛NOIP2010]集卡片

贪心，坑了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define M 2010
#define N 1000010
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
int n,m,i,p,F[M],times[N],a[N],t[M],v,sum[N];
inline int getint()
{
    register int num=0;
    register char ch;
    do ch=getchar(); while (ch<'0' || ch>'9');
    do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
    return num;
... Read more »
Views: 460 | Added by: dhy0077 | Date: 10.16.2013

[模拟赛NOIP2010]喜欢宠物的 GF

哈哈，想到了。

若不考虑直接召唤，这显然是棵生成树。

若A能召唤B，添加一条边从A到B，

权值为代价，这条边显然是无向的。

然后直接召唤怎么办呢？

想想，直接召唤的东西是从哪里来的？

有时候，就是要天真一点。

建空节点吧！！！然后kruskal，然后就没有然后了。

时间复杂度为O(NE+ElogE)

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<set>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<iostream>

#include<string>

... Read more »

Views: 446 | Added by: dhy0077 | Date: 10.16.2013