| Section 3.3 | DONE | 2013.01.07 | TEXT Eulerian Tours |
| DONE | 2012.09.28 | PROB Riding The Fences [ANALYSIS] | |
| DONE | 2012.09.28 | PROB Shopping Offers [ANALYSIS] | |
| DONE | 2012.09.29 | PROB Camelot [ANALYSIS] | |
| DONE | 2012.09.30 | PROB Home on the Range [ANALYSIS] | |
| DONE | 2012.09.30 | PROB A Game [ANALYSIS] |
Riding The Fences
寻找欧拉路径或欧拉回路，用TEXT Eulerian Tours中的算法可以完美解决。
/*
ID: huilong1
LANG: C++
TASK: fence
*/
#include<stdio.h>
#include<stdlib.h>
int map[501][501];
int degree[501];
int tour[1025];
int tail;
int F;
FILE *fin,*fout;
void search(int s){
if(degree[s]==0){
tour[tail++]=s;
}
else{
int i;
for(i=1;i<=500;i++){
if(map[s][i]){
degree[s]--;
map[s][i]--;
map[i][s]--;
search(i);
}
}
tour[tail++]=s;
}
}
int main(){
fin=fopen("fence.in","r");
fout=fopen("fence.out","w");
fscanf(fin,"%d",&F);
while(F){
int u,v;
fscanf(fin,"%d %d",&u,&v);
map[u][v]++;
map[v][u]++;
degree[u]++;
degree[v]++;
F--;
}
int s=0,i;
for(i=1;i<=500;i++){
if(s==0&°ree[i]>0)s=i;
if(degree[i]%2){
s=i;
break;
}
}
search(s);
for(i=tail-1;i>=0;i--)
fprintf(fout,"%d\n",tour[i]);
return 0;
}
以下出自usaco training：
Detecting whether a graph has an Eulerian tour or circuit is actually easy; two different rules apply.
☉A graph has an Eulerian circuit if and only if it is connected (once you throw out all nodes of degree 0) and every node has `even degree'.
☉A graph has an Eulerian path if and only if it is connected and every node except two has even degree.
☉In the second case, one of the two nodes which has odd degree must be the start node, while the other is the end node.
The basic idea of the algorithm is to start at some node the graph and determine a circuit back to that same node. Now, as the circuit is added (in reverse order, as it turns out), the algorithm ensures that all the edges of all the nodes along that path have been used. If there is some node along that path which has an edge that has not been used, then the algorithm finds a circuit starting at that node which uses that edge and splices this new circuit into the current one. This continues until all the edges of every node in the original circuit have been used, which, since the graph is connected, implies that all the edges have been used, so the resulting circuit is Eulerian.
More formally, to determine a Eulerian circuit of a graph which has one, pick a starting node and recurse on it. At each recursive step:
Pick a starting node and recurse on that node. At each step:
If the node has no neighbors, then append the node to the circuit and return
If the node has a neighbor, then make a list of the neighbors and process them (which includes deleting them from the list of nodes on which to work) until the node has no more neighbors
To process a node, delete the edge between the current node and its neighbor, recurse on the neighbor, and postpend the current node to the circuit.
And here's the pseudocode:
# circuit is a global array
find_euler_circuit
circuitpos = 0
find_circuit(node 1)
# nextnode and visited is a local array
# the path will be found in reverse order
find_circuit(node i)
if node i has no neighbors then
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
else
while (node i has neighbors)
pick a random neighbor node j of node i
delete_edges (node j, node i)
find_circuit (node j)
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it.
Both of these algorithms run in O(m + n) time, where m is the number of edges and n is the number of nodes, if you store the graph in adjacency list form. With larger graphs, there's a danger of overflowing the run-time stack, so you might have to use your own stack.
Multiple edges between nodes can be handled by the exact same algorithm.
Self-loops can be handled by the exact same algorithm as well, if self-loops are considered to add 2 (one in and one out) to the degree of a node.
A directed graph has a Eulerian circuit if it is strongly connected (except for nodes with both in-degree and out-degree of 0) and the indegree of each node equals its outdegree. The algorithm is exactly the same, except that because of the way this code finds the cycle, you must traverse arcs in reverse order.
Finding a Eulerian path in a directed graph is harder. Consult Sedgewick if you are interested.
Shopping Offers
五维的背包问题
/*
ID: huilong1
LANG: C++
TASK: shopping
*/
#include<stdio.h>
#include<stdlib.h>
#define IMPOSSIBLE (0x7fffffff)
FILE *fin,*fout;
int numoffer;
int offer[105][5];
int price[105];
int s,b;
int need[5];
int hash[5];
int memo[100][12];
int dp[6][6][6][6][6][100];
int gethash(int c){
int i;
for(i=0;i<b;i++)
if(c==hash[i])
return i;
return -1;
}
int main(){
fin=fopen("shopping.in","r");
fout=fopen("shopping.out","w");
fscanf(fin,"%d",&s);
int i,j,k,l,m,n;
for(i=0;i<s;i++){
fscanf(fin,"%d",&memo[i][0]);
for(j=1;j<=memo[i][0];j++){
fscanf(fin,"%d %d",&memo[i][(j-1)*2+1],&memo[i][(j-1)*2+2]);
}
fscanf(fin,"%d",&memo[i][2*memo[i][0]+1]);
}
fscanf(fin,"%d",&b);
for(i=0;i<b;i++){
fscanf(fin,"%d %d %d",&hash[i],&need[i],&price[i+1]);
offer[i+1][i]=1;
}
numoffer=b;
for(i=0;i<s;i++){
numoffer++;
for(j=1;j<=memo[i][0];j++){
int hashcode=gethash(memo[i][(j-1)*2+1]);
if(hashcode==-1)break;
offer[numoffer][hashcode]=memo[i][(j-1)*2+2];
}
if(j<=memo[i][0]){
numoffer--;
continue;
}
price[numoffer]=memo[i][2*memo[i][0]+1];
}
for(n=0;n<=numoffer;n++)
for(i=0;i<=need[0];i++)
for(j=0;j<=need[1];j++)
for(k=0;k<=need[2];k++)
for(l=0;l<=need[3];l++)
for(m=0;m<=need[4];m++){
if(i+j+k+l+m>0&&n==0)
dp[i][j][k][l][m][n]=IMPOSSIBLE;
if(n>0){
dp[i][j][k][l][m][n]=dp[i][j][k][l][m][n-1];
int pi,pj,pk,pl,pm;
pi=i-offer[n][0];
pj=j-offer[n][1];
pk=k-offer[n][2];
pl=l-offer[n][3];
pm=m-offer[n][4];
if(pi>=0&&pj>=0&&pk>=0&&pl>=0&&pm>=0){
if(dp[pi][pj][pk][pl][pm][n]!=IMPOSSIBLE){
if(dp[pi][pj][pk][pl][pm][n]+price[n]<dp[i][j][k][l][m][n])
dp[i][j][k][l][m][n]=dp[pi][pj][pk][pl][pm][n]+price[n];
}
}
}
}
fprintf(fout,"%d\n",dp[need[0]][need[1]][need[2]][need[3]][need[4]][numoffer]);
return 0;
}
Camelot
需要细心的剪枝优化，可以做优化的地方主要在于骑士接王的位置。为了让骑士接到王，王可以做一些预先的移动，其中王通过两步像骑士一样走一个“日”字显然和骑士走两次“日”字步数相同，基于此可以对王的移动中包含，或者等效包含“日”字的情况剪枝。比如在8*8的棋盘上，王的位置用K表示，除了王的原位置之外，需要枚举的骑士接王的位置用*表示，其余点用0表示则有下图：
/*
ID: huilong1
LANG: C++
TASK: camelot
*/
#include<stdio.h>
#include<stdlib.h>
#define LENQUE 781
#define INFI 500
FILE *fin,*fout;
int R,C;
int dist[781][31][27];
int total[31][27];
int distking[31][27];
int distride[120][31][27];
int numride;
int king[2];
int numknight;
int knight[781][2];
int moveknight[8][2]={
{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}
};
int moveking[8][2]={
{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}
};
int queue[LENQUE][3];
bool done[31][27];
void bfs(int s[2],int move[8][2],int distmemo[31][27]){
int i,j;
for(i=0;i<R;i++)for(j=0;j<C;j++)done[i][j]=false;
for(i=0;i<R;i++)for(j=0;j<C;j++)distmemo[i][j]=INFI;
distmemo[s[0]][s[1]]=0;
done[s[0]][s[1]]=true;
int head=0,tail=1;
queue[0][0]=s[0];
queue[0][1]=s[1];
queue[0][2]=0;
while(head!=tail){
for(i=0;i<8;i++){
int temp[2];
temp[0]=queue[head][0]+move[i][0];
temp[1]=queue[head][1]+move[i][1];
if(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<=C){
if(!done[temp[0]][temp[1]]){
queue[tail][0]=temp[0];
queue[tail][1]=temp[1];
queue[tail][2]=queue[head][2]+1;
done[temp[0]][temp[1]]=true;
distmemo[temp[0]][temp[1]]=queue[tail][2];
tail=(tail+1)%LENQUE;
}
}
}
head=(head+1)%LENQUE;
}
}
int main(){
fin=fopen("camelot.in","r");
fout=fopen("camelot.out","w");
fscanf(fin,"%d %d\n",&R,&C);
char col;
int row;
fscanf(fin,"%c %d",&col,&row);
king[0]=row-1;
king[1]=col-'A';
while(fscanf(fin,"%c",&col)!=EOF){
if(col==' '||col=='\n')continue;
fscanf(fin,"%d",&row);
knight[numknight][0]=row-1;
knight[numknight][1]=col-'A';
numknight++;
}
int i;
bfs(king,moveking,distking);
for(i=0;i<8;i++){
int temp[2];
temp[0]=king[0]+moveking[i][0];
temp[1]=king[1]+moveking[i][1];
while(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<C){
bfs(temp,moveknight,distride[numride++]);
temp[0]=temp[0]+moveking[i][0];
temp[1]=temp[1]+moveking[i][1];
}
}
bfs(king,moveknight,distride[numride++]);
for(i=0;i<numknight;i++){
bfs(knight[i],moveknight,dist[i]);
}
int min=0x7fffffff;
int gr,gc,ride,d,move;
for(gr=0;gr<R;gr++)for(gc=0;gc<C;gc++){
for(i=0;i<numknight;i++){
total[gr][gc]+=dist[i][gr][gc];
}
}
for(gr=0;gr<R;gr++)for(gc=0;gc<C;gc++){
d=distking[gr][gc]+total[gr][gc];
if(d<min)min=d;
for(ride=0;ride<numknight;ride++){
d=distride[numride-1][gr][gc];
d+=dist[ride][king[0]][king[1]];
d+=total[gr][gc]-dist[ride][gr][gc];
if(d<min)min=d;
int po=0,countking=0;
for(i=0;i<8;i++){
int temp[2];
temp[0]=king[0]+moveking[i][0];
temp[1]=king[1]+moveking[i][1];
countking=1;
while(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<C){
d=distride[po][gr][gc];
d+=countking;
d+=dist[ride][temp[0]][temp[1]];
d+=total[gr][gc]-dist[ride][gr][gc];
if(d<min)min=d;
po++;
countking++;
temp[0]=temp[0]+moveking[i][0];
temp[1]=temp[1]+moveking[i][1];
}
}
}
}
fprintf(fout,"%d\n",min);
return 0;
}
Home on the Range
动态规划，用dp[i][j][n]表示以点(i,j)为右下角，有没有一个边长为n的正方形区域。
则dp[i][j][n]=dp[i-1][j][n-1]&&dp[i][j-1][n-1]&&dp[i-1][j-1][n-1]&&dp[i][j][1]
/*
ID: huilong1
LANG: C++
TASK: range
*/
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int N;
int dp[251][251];
bool map[251][251];
int main(){
fin=fopen("range.in","r");
fout=fopen("range.out","w");
fscanf(fin,"%d\n",&N);
int i,j,n;
for(i=1;i<=N;i++)for(j=1;j<=N;j++){
char c;
fscanf(fin,"%c",&c);
if(c=='\n')
fscanf(fin,"%c",&c);
if(c=='1')map[i][j]=true;
else map[i][j]=false;
}
for(n=2;n<=N;n++){
for(i=N;i>=n;i--)for(j=N;j>=n;j--){
map[i][j]=map[i-1][j-1]&&map[i-1][j]&&map[i][j-1]&&map[i][j];
}
for(i=0;i<=N;i++)dp[i][n-1]=0;
for(j=0;j<=N;j++)dp[n-1][j]=0;
for(i=n;i<=N;i++)for(j=n;j<=N;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
}
if(dp[N][N])fprintf(fout,"%d %d\n",n,dp[N][N]);
}
return 0;
}
A Game
动态规划，用dp[i][j]表示对于从第i到第j的一个整数序列，先手的最优分数，total[i][j]表示从第i到第j的一个整数序列的总分数（即所有整数的和），board[i]表示第i个整数的值，则有
dp[i][j]=max{
board[i]+(total[i+1][j]-dp[i+1][j]),
board[j]+(total[i][j-1]-dp[i][j-1])
}
/*
ID: huilong1
LANG: C++
TASK: game1
*/
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
int N;
int board[101];
int dp[101][101];
int total[101];
int main(){
fin=fopen("game1.in","r");
fout=fopen("game1.out","w");
fscanf(fin,"%d",&N);
int i,j,l;
for(i=1;i<=N;i++){
fscanf(fin,"%d",&board[i]);
dp[i][i]=board[i];
total[i]=total[i-1]+board[i];
}
for(l=2;l<=N;l++){
for(i=1;i+l-1<=N;i++){
j=i+l-1;
dp[i][j]=board[i]+(total[j]-total[i]-dp[i+1][j]);
int t=board[j]+(total[j-1]-total[i-1]-dp[i][j-1]);
if(t>dp[i][j])dp[i][j]=t;
}
}
fprintf(fout,"%d %d\n",dp[1][N],total[N]-dp[1][N]);
return 0;
}
.gif)
