POJ 1950 Dessert
比较简单，但是要细心。
这道题关键注意运算一个给定的表达式。我的是用两个栈实现，一个数字栈，一个操作符栈。
其次，题目规模<=15，所以可以全体打表。也可以将结果个数打表，表达式搜索，当搜出结果
超过20时，马上退出。
参考程序：
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std ;
typedef __int64 lld ;
const char opech[] ="+-." ;
const lld maxn = 20 ;
const lld table[] = {0,0,0,1,1,1,1,6,10,11,17,88,162,197,437,1350} ;
lld n ;
lld s1[maxn] , s2[maxn] , t1 , t2 ;
lld comp(lld xx[]){
lld i , ans;
t1 = t2 = 0 ; s1[t1++] = 1 ;
for(i = 2 ; i<=n ; ++i)
if(xx[i] == 2)
s1[t1-1] = s1[t1-1]*( i<10 ? 10 : 100) + i ;
else
s1[t1++] = i , s2[t2++] = xx[i] ;
for(i = 0 , ans = s1[0] ; i < t2 ; ++ i)
ans = ans + (s2[i]==0 ? s1[i+1] : -s1[i+1]) ;
return ans ;
}
lld x[maxn] , res_cnt ;
void dfs(int dep ){
lld i ;
if(res_cnt > 20 ) return ;
if(dep > n ){
if(comp(x) || ++res_cnt > 20) return ;
printf("1");
for(i = 2 ; i <=n ; ++ i)
printf(" %c %I64d",opech[x[i]],i);
printf("\n");
return ;
}
for(i = 0 ; i < 3 ; ++ i){
x[dep] = i ;
dfs(dep + 1);
}
}
int main(){
scanf("%I64d",&n);
res_cnt = 0 ;
dfs(2);
printf("%I64d\n",table[n]);
return 0 ;
}
POJ 3414 Pots
简单BFS题，细心模拟即可。
一边搜索，一边记录路径信息，便于搜索得到解路径。
可惜我编了40分钟！
参考程序：
#include<iostream>
#include<stdlib.h>
#include<queue>
using namespace std ;
const int maxn = 105 ;
struct node{
int a ,b;
node(){}
node(int ia,int ib):
a(ia) , b(ib) {}
};
node ed(-1,-1);
int used[maxn][maxn][3];
int A , B , C ;
void cmd(int i){
switch(i){
case 0: printf("FILL(1)\n"); break;
case 1: printf("FILL(2)\n"); break;
case 2: printf("DROP(1)\n"); break;
case 3: printf("DROP(2)\n"); break;
case 4: printf("POUR(1,2)\n"); break;
case 5: printf("POUR(2,1)\n"); break;
}
}
node extend(node st , int i){
int ab = min(B-st.b,st.a), ba = min(A-st.a ,st.b) ;
switch(i){
case 0: return node(A , st.b);
case 1: return node(st.a , B);
case 2: return node(0 , st.b);
case 3: return node(st.a , 0);
case 4: return node(st.a - ab , st.b + ab);
case 5: return node(st.a + ba , st.b - ba);
}
}
void solve(int x,int y){
if(used[x][y][1] == 0){
cmd(used[x][y][2]) ; return ;
}
solve(used[x][y][1]/maxn, used[x][y][1]%maxn);
cmd(used[x][y][2]);
}
int bfs(){
int step = 1 , i , x , y;
queue<node>Q;
node st(0,0) , nxt ;
memset(used,-1,sizeof(used));
used[st.a][st.b][0]=0 ;
Q.push(st) ; Q.push(ed) ;
while(!Q.empty()){
st = Q.front() ; Q.pop() ;
if(st.a == -1 ){
if(Q.empty()) return 0 ;
st = Q.front() ; Q.pop() ;
Q.push(ed); ++step ;
}
for(i = 0 ; i < 6 ; ++ i){
nxt = extend(st,i);
if(used[nxt.a][nxt.b][0]!=-1 ) continue ;
used[nxt.a][nxt.b][0] = step ;
used[nxt.a][nxt.b][1] = st.a * maxn + st.b ;
used[nxt.a][nxt.b][2] = i ;
if(nxt.a == C || nxt.b == C){
printf("%d\n",step);
solve(nxt.a,nxt.b);
return 1 ;
}
Q.push(nxt);
}
}
return 0 ;
}
int main(){
while(scanf("%d%d%d",&A,&B,&C)!=EOF)
if(C == 0)
printf("0");
else if(!bfs())
printf("impossible\n");
return 0 ;
}
HNNUOJ 10743 Shopping
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10743&courseid=43
给10000个点，50000条边，求从0出发经给定10个点后回到0点的最短路径：
只要综合一下各个算法即可：
（1） 用SPFA求出11个点为源的最短路。
（2） 再用dfs求一次TSP即可。
参考程序：
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std ;
typedef __int64 lld ;
const int MaxN = 100005 ;
const int MaxE = 500005 ;
const int MaxS = 15 ;
const lld INF = (lld)1<<62 ;
struct node
{
int y , c ,next ;
};
int es , hd[MaxN] , N , M , S , shop[MaxS] ;
lld dist[MaxN] , cd[MaxS][MaxS];
node e[MaxE] ;
bool vis[MaxN] ;
void SPFA(int t){
int i , v , u ;
queue<int> Q ;
for(i = 0 ; i<N ; ++i)
vis[i] = 0 , dist[i] = INF ;
dist[t] = 0 ; vis[t] = 1 ; Q.push(t);
while(!Q.empty()){
v = Q.front() ; Q.pop() ; vis[v] = 0 ;
for(i = hd[v] ; i!=-1 ; i=e[i].next)
if(dist[u = e[i].y ] > dist[v] + (lld)e[i].c ) {
dist[u] = dist[v] + (lld)e[i].c ;
if(!vis[u])
vis[u] = 1 , Q.push(u);
}
}
}
lld best , mindist ;
int x[MaxS] ;
void dfs(int ty , int dep){
if(dep == S){
best = min(best , ty + cd[x[S-1]][0]);
return ;
}
int i ;
for(i = dep ; i < S ; ++i){
swap(x[dep] , x[i]);
if(ty + (S - i) * mindist < best)
dfs(ty + cd[ x[dep-1] ][ x[dep] ] , dep + 1);
swap(x[dep] , x[i]);
}
}
void work(){
int i , j ;
for(i = 0 ; i < S ; ++i){
SPFA(shop[i]);
for(j = 0 ; j < S ; ++j)
cd[i][j] = dist[shop[j]] ;
}
best = cd[S-1][0] ; mindist = INF ;
for(i = 0 ; i < S-1 ; ++ i) best +=cd[i][i+1];
for(i = 0 ; i < S ; ++ i) x[i] = i ;
for(i = 0 ; i < S ; ++ i)
for(j = 0 ; j < S ; ++j)
mindist = mindist < cd[i][j] ? mindist : cd[i][j] ;
dfs(0,1);
printf("%I64d\n",best);
}
int main(){
int tst , i , x , y ,c;
scanf("%d",&tst);
while(tst--){
scanf("%d%d",&N,&M);
es = 0 ; memset(hd,-1,sizeof(hd));
for(i = 0 ; i<M ; ++ i){
scanf("%d%d%d",&x,&y,&c);
e[es].y = y , e[es].c = c ; e[es].next = hd[x] ; hd[x] = es ++ ;
e[es].y = x , e[es].c = c ; e[es].next = hd[y] ; hd[y] = es ++ ;
}
scanf("%d",&S);
++S ; shop[0] = 0 ;
for(i = 1 ; i<S ; ++i)
scanf("%d",&shop[i]);
work();
}
return 0 ;
}