damage
构造
不错的图论基础题。首先，如果第i头牛报告它所在的结点未损坏但无法返回牛棚，那么所有地震后与i连通的结点都不能与牛棚连通，否则牛i就可以先到这个结点再返回牛棚。由于我们希望与牛棚不连通的结点数尽可能少，于是我们尽可能让结点与牛棚连通。如果第i头牛报告它所在的结点未损坏但无法返回牛棚，由于地震不破坏边，所以与结点i相邻的结点地震后一定仍能到达结点i，因此它们一定不与牛棚连通。除此之外，其它结点都可能与牛棚连通，这样对于每个报告，我们将与之相邻的结点标记为与牛棚不连通。最后从牛棚开始在剩余结点上floodfill，能到达的结点为真正能于牛棚连通的结点。
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 | /* ID: lipeiqi1 LANG: C++ PROB: damage */ #include <cstdio> struct edge { int v; edge *next; edge(int v,edge *next):v(v),next(next) {} } *e[30003]; bool u[30003]; int ans; void dfs(int v) { if(u[v]) return; u[v]=true; --ans; for(edge *t=e[v];t;t=t->next) dfs(t->v); } int main() { freopen("damage.in","r",stdin); freopen("damage.out","w",stdout); int p,c,n,a,b; scanf("%d %d %d",&p,&c,&n); for(int i=0;i<c;++i) { scanf("%d %d",&a,&b); e[a]=new edge(b,e[a]); e[b]=new edge(a,e[b]); } for(int i=0;i<n;++i) { scanf("%d",&b); for(edge *t=e[b];t;t=t->next) u[t->v]=true; } ans=p; dfs(1); printf("%d\n",ans); return 0; } |
baric
动态规划
f[i][j]表示前i个数中选出j个数作为子集并且第i个数一定入选子集的最小错误值，那么题中计算错误值的条件1对f[i][1]进行初始化，利用条件2进行状态转移求出f[i][j]，最后对于每个f[i][j]，将[i+1..n]造成的错误值考虑进来加到f[i][j]上去，枚举可求得错误值不超过限制的最小子集大小以及最小错误值。
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 | /* ID: lipeiqi1 LANG: C++ PROB: baric */ #include <iostream> using namespace std; int d[101],f[101][101],s[101][101]; int main() { freopen("baric.in","r",stdin); freopen("baric.out","w",stdout); int n,e; scanf("%d %d",&n,&e); for(int i=1;i<=n;++i) scanf("%d",d+i); for(int i=1;i<=n;++i) for(int j=1;j<i;++j) f[i][1]+=abs(d[i]-d[j])<<1; for(int i=1;i<n;++i) for(int j=i+2;j<=n;++j) for(int k=i+1;k<j;++k) s[i][j]+=abs((d[k]<<1)-d[i]-d[j]); for(int i=2;i<=n;++i) for(int j=2;j<=i;++j) { f[i][j]=f[i-1][j-1]; for(int k=i-2;k>0;--k) f[i][j]=min(f[i][j],f[k][j-1]+s[k][i]); } for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) for(int k=i+1;k<=n;++k) f[i][j]+=abs(d[i]-d[k])<<1; int minNum=n,minErr=INT_MAX; for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) if(f[i][j]<=e) if(j<minNum) minNum=j,minErr=f[i][j]; else if(j==minNum) minErr=min(minErr,f[i][j]); printf("%d %d\n",minNum,minErr); return 0; } |
travel
图论综合题
由于题目保证从结点1到其它任何结点的最短路径唯一，结点1到其它结点的最短路径一定构成唯一的一棵最短路生成树。借助Dijkstra+普通二项堆可以在O(mlogm)的时间内构造最短路生成树。
接下来我们要做的就是求不经过最后一条边的次短路。从根(结点1)到每个结点路径上的最后一条边不能使用，我们需要从根先到某个中间结点中转到达最终结点，中间结点可以直接和最终结点相连，也可以作为最终结点的子孙顺着生成树中的路径到达最终结点。对于最短路生成树中的叶结点来说，将所有与之相邻的结点分别作为中间结点考虑，用堆来维护最小值即可；对于非叶结点来说，我们既需要考虑所有与之相邻的结点作为中间结点（类似叶结点仍然用堆维护），也需要考虑那些经过他直接孩子结点的路径（也就是中间结点作为子孙的情况），这时我们可以把求解孩子结点时的堆合并起来并每项都加上到对应孩子结点的边权。但是此时堆中可能存在一些无效路径，因为在子孙结点时可能使用这个结点本身或某个其它子孙作为中间结点，这些路径应该删去。至此问题解决，具体实现的时候有一个技巧可以避免合并堆的时候每一项都要加上一个值，那就是在堆中存储的每项都加上从根到这个结点的距离，最后输出时再减去这个距离值，这样保证求解到某个祖先结点时正好相当于加上了对应边权值而又不影响最终结果。
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 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 | /* ID: lipeiqi1 LANG: C++ PROG: travel */ #include <iostream> #include <set> using namespace std; const int MAXN=100011; struct edge { int v,w; edge *next; edge(int v,int w,edge *next):v(v),w(w),next(next) {} } *e[MAXN],*child[MAXN]; struct THeap { int v,d; } heap[MAXN]; int heapsize,k,n,timestamp,pos[MAXN],dis[MAXN],f[MAXN],num[MAXN],father[MAXN],ans[MAXN]; bool visited[MAXN]; multiset < pair<int,int> > d[MAXN]; inline int findRoot(int v) { while(f[v]!=v) v=f[v]=f[f[v]]; return v; } void unite(int x,int y) { x=findRoot(x),y=findRoot(y); if(x==y) return; if(d[x].size()<d[y].size()) { d[y].insert(d[x].begin(),d[x].end()); d[x].clear(); f[x]=y; } else { d[x].insert(d[y].begin(),d[y].end()); d[y].clear(); f[y]=x; } } void downMaintain(int k) { int i=k; THeap x=heap[k]; for(int j=k<<1;j<=heapsize;) { if(j<heapsize&&heap[j].d>heap[j+1].d) j++; if(x.d<=heap[j].d) break; heap[i]=heap[j]; pos[heap[j].v]=i; i=j; j=i<<1; } heap[i]=x; pos[heap[i].v]=i; } void heapUpdate(int v,int dis) { int i=pos[v]; if(i&&heap[i].d<=dis) return; if(!i) i=++heapsize; for(;i!=1&&dis<heap[i>>1].d;i>>=1) heap[i]=heap[i>>1],pos[heap[i>>1].v]=i; heap[i].v=v; heap[i].d=dis; pos[v]=i; } void deleteMin() { pos[heap[1].v]=0; heap[1]=heap[heapsize--]; downMaintain(1); } void dijkstra(int vstart=1) { int pv,pdis; heapUpdate(vstart,0); for(int i=0;i<n;i++) { do { pv=heap[1].v,pdis=heap[1].d; deleteMin(); } while(visited[pv]); visited[pv]=true; dis[pv]=pdis; for(edge *t=e[pv];t;t=t->next) if(!visited[t->v]) heapUpdate(t->v,pdis+t->w); } } void dfs(int v) { num[v]=++timestamp; for(edge *t=child[v];t;t=t->next) { dfs(t->v); unite(v,t->v); } int c=findRoot(v); for(edge *t=e[v];t;t=t->next) if(t->v!=father[v]) { if(!visited[t->v]||num[t->v]<num[v]) d[c].insert(make_pair(dis[v]+dis[t->v]+t->w,t->v)); else { multiset<pair<int,int> >::iterator p=d[c].find(make_pair(dis[v]+dis[t->v]+t->w,v)); if(p!=d[c].end()) d[c].erase(p); } } visited[v]=true; while(!d[c].empty()&&(visited[d[c].begin()->second]&&num[d[c].begin()->second]>num[v])) d[c].erase(d[c].begin()); if(d[c].empty()) ans[v]=-1; else ans[v]=d[c].begin()->first; } int main() { freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); int m,a,b,w; for(scanf("%d %d",&n,&m);m;--m) { scanf("%d %d %d",&a,&b,&w); e[a]=new edge(b,w,e[a]); e[b]=new edge(a,w,e[b]); } dijkstra(); for(int i=1;i<=n;++i) for(edge *t=e[i];t;t=t->next) if(dis[i]+t->w==dis[t->v]) { father[t->v]=i; child[i]=new edge(t->v,t->w,child[i]); } for(int i=1;i<=n;++i) f[i]=i; memset(visited,false,sizeof(visited)); dfs(1); for(int i=2;i<=n;++i) printf("%d\n",ans[i]==-1?-1:ans[i]-dis[i]); return 0; } |
为什么没有第三题 travel呢?
[Reply]
To zqzas:
第三题很快就会有的
[Reply]
To zqzas:
已经有了…
[Reply]
我用spfa竟然超时.
[Reply]
我的blog:
http://www.zqzas.cn
email/gtalk:zqzas1@gmail.com
[Reply]