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[]; int main()
{
scanf("%d",&n);
for(int i=; i<n; i++)
scanf("%d",&a[i]);
vector< int > v(a,a+n);
make_heap(v.begin(),v.end(),greater< int >());
long long ans=;
for(int i=; i<=n-; 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 ;
}
POJ 3254 Corn Fields 状态压缩递推
uc[]表示相邻两位不同时为1的情况，377种，因此n*377^2即可
注意，位运算优先级是低于==的！
#include <cstdio>
#include <cstring>
#define MOD 100000000 int n,m,a[],k;
int uc[],all;
int f[][]; int main()
{
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
for(int j=; j<m; j++)
{
scanf("%d",&k);
a[i]=(a[i]<<)+k;
}
for(int i=; i<(<<m); i++)
{
int tmi=i,flag=;
while(tmi)
{
if((tmi&)==) flag=;
tmi>>=;
}
if(!flag)
{
uc[all++]=i;
if((i|a[])==a[])
f[][i]=;
}
} for(int i=; i<n; i++)
for(int j=; j<all; j++)
if((a[i]|uc[j])==a[i])
{
for(int k=; k<all; k++)
if(!(uc[j]&uc[k]))
{
f[i][uc[j]]=(f[i][uc[j]]+f[i-][uc[k]])%MOD;
}
} int ans=;
for(int j=; j<all; j++)
ans=(ans+f[n-][uc[j]])%MOD;
printf("%d\n", ans);
return ;
}
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 0x3f3f3f3f using namespace std; struct Edge
{
int y,w,ne;
}e[]; int x,y,w,n,m;
int be[],all;
int h[];
bool vis[]; 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=; i<=n; i++)
{
h[i]=INF;
vis[i]=;
}
h[s]=;
vis[s]=;
while(!q.empty())
q.pop();
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
for(int i=be[u]; i!=-; 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]=;
q.push(v);
}
}
}
}
} int Astar(int s, int t, int k)
{
SPFA(t);
priority_queue< Point > q;
while(!q.empty())
q.pop();
memset(vis,,sizeof(vis));
Point cur,nxt;
cur.x=s;
cur.g=;
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!=-; i=e[i].ne)
{
nxt.x=e[i].y;
nxt.g=cur.g+e[i].w;
q.push(nxt);
}
}
return -;
} void init()
{
all=;
memset(be,-,sizeof(be));
} int main()
{
scanf("%d%d",&n,&m);
init();
for(int i=; i<m; i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
printf("%d\n",Astar(,n,));
return ;
}