刷刷POI，整个人都POI！
BZOJ 1098: [POI2007]办公楼biu 补图联通块直接DFS出来就行了，很容易TLE要用链表及时删点、
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; const int Maxm=2000010; inline int read(){ int x = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x; } struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; int head[Maxn]; Edge e[Maxm*2]; int nume; int n,m; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]);head[u]=nume; e[++nume]=Edge(u,head[v]);head[v]=nume; } int nxt[Maxn],pre[Maxn]; inline void del(int x){ int tmp=pre[x]; nxt[tmp]=nxt[x]; pre[nxt[x]]=tmp; } bool vis[Maxn]; int cnt; int siz[Maxn]; bool noEdge[Maxn]; int que[Maxn]; int l,r; int i; void bfs(int src){ que[0]=src; vis[src]=true; for (l = r = 0; l <= r; ++l){ int x=que[l]; //printf("%d\n",x); siz[cnt]++; for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true; for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i] && !noEdge[i]){ del(i); vis[i]=true; que[++r]=i; } } for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false; } } inline void input(){ freopen("1098.in","r",stdin); //freopen("1098.out","w",stdout); } int main(){ //input(); n=read();m=read(); int x,y; for (i=1;i<=m;i++){ x=read(),y=read(); addEdge(x,y); } for (i=0;i<=n;i++){ nxt[i]=i+1; pre[i+1]=i; } for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i]){ cnt++; del(i); bfs(i); } } sort(siz+1,siz+cnt+1); printf("%d\n",cnt); for (i=1;i<=cnt;i++){ printf("%d ",siz[i]); } printf("\n"); return 0; } |
BZOJ 1097: [POI2007]旅游景点atr 首先SPFA出前k+1个点的最短路,然后做状压DP. pre […]
