首页 > 代码库 > USACO 2006 November Gold
USACO 2006 November Gold
POJ 3253 Fence Repair STL堆操作
我想说，STL里堆是我目前见到最蛋疼的操作。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))using namespace std;int n,a[20005];int main(){ scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&a[i]); vector< int > v(a,a+n); make_heap(v.begin(),v.end(),greater< int >()); long long ans=0; for(int i=1; i<=n-1; i++) { long long tmp=v.front(); pop_heap(v.begin(),v.end(),greater< int >()); v.pop_back(); tmp+=v.front(); pop_heap(v.begin(), v.end(),greater< int >()); v.pop_back(); v.push_back(tmp); push_heap(v.begin(),v.end(),greater< int >()); ans+=tmp; printf("%d\n", tmp); } printf("%lld\n",ans); return 0;}
POJ 3254 Corn Fields 状态压缩递推
uc[]表示相邻两位不同时为1的情况，377种，因此n*377^2即可
注意，位运算优先级是低于==的！
#include <cstdio>#include <cstring>#define MOD 100000000int n,m,a[20],k;int uc[500],all;int f[20][5000];int main(){ scanf("%d%d",&n,&m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { scanf("%d",&k); a[i]=(a[i]<<1)+k; } for(int i=0; i<(1<<m); i++) { int tmi=i,flag=0; while(tmi) { if((tmi&3)==3) flag=1; tmi>>=1; } if(!flag) { uc[all++]=i; if((i|a[0])==a[0]) f[0][i]=1; } } for(int i=1; i<n; i++) for(int j=0; j<all; j++) if((a[i]|uc[j])==a[i]) { for(int k=0; k<all; k++) if(!(uc[j]&uc[k])) { f[i][uc[j]]=(f[i][uc[j]]+f[i-1][uc[k]])%MOD; } } int ans=0; for(int j=0; j<all; j++) ans=(ans+f[n-1][uc[j]])%MOD; printf("%d\n", ans); return 0;}
POJ 3255 A*算法求第k短路
第一次接触A*，了解了下。
—————————————————维基百科————————————————————————————
如果以 g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离，那么 A*算法的公式为：f(n)=g(n)+h(n)。 这个公式遵循以下特性：
- 如果h(n)为0，只需求出g(n)，即求出起点到任意顶点n的最短路径，则转化为单源最短路径问题，即Dijkstra算法
- 如果h(n)<=“n到目标的实际距离”，则一定可以求出最优解。而且h(n)越小，需要计算的节点越多，算法效率越低。
—————————————————————————————————————————————————
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3fusing namespace std;struct Edge{ int y,w,ne;}e[200005];int x,y,w,n,m;int be[5005],all;int h[5005];bool vis[5005];struct Point{ int x,g; bool operator < (const Point T) const { return g+h[x]>T.g+h[T.x]; }};void add(int x, int y, int w){ e[all].y=y; e[all].w=w; e[all].ne=be[x]; be[x]=all++;}void SPFA(int s){ queue< int > q; for(int i=0; i<=n; i++) { h[i]=INF; vis[i]=0; } h[s]=0; vis[s]=1; while(!q.empty()) q.pop(); q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=be[u]; i!=-1; i=e[i].ne) { int v=e[i].y; if(h[v]>h[u]+e[i].w) { h[v]=h[u]+e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } }}int Astar(int s, int t, int k){ SPFA(t); priority_queue< Point > q; while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); Point cur,nxt; cur.x=s; cur.g=0; q.push(cur); while(!q.empty()) { cur=q.top(); q.pop(); if(cur.x==t && !--k) return cur.g; for(int i=be[cur.x]; i!=-1; i=e[i].ne) { nxt.x=e[i].y; nxt.g=cur.g+e[i].w; q.push(nxt); } } return -1;}void init(){ all=0; memset(be,-1,sizeof(be));}int main(){ scanf("%d%d",&n,&m); init(); for(int i=0; i<m; i++) { scanf("%d%d%d",&x,&y,&w); add(x,y,w); add(y,x,w); } printf("%d\n",Astar(1,n,2)); return 0;}
USACO 2006 November Gold
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。