403
poj 2090 Two-Stacks Solitaire
這道題不是特別簡單，我自己考慮了很久，未果。於是希望在網絡上找到參考，但是網上參考不多
題意：給一個數列，兩個棧，要求數列從後往前依次入棧，問能否使出棧序列是不減的。（雙棧排序）
分析：利用二分圖染色法。
首先觀察那些牌絕對不能壓入同一個棧，若兩個不能入同一棧則連一條邊，然後根據二分圖染色，看是否能構成二分圖。如果不能直接輸出impossible
兩張牌i,j不能入同一棧的充要條件是，i>j>k（i最先入棧） && a[k]<a[i]<a[j]
然後根據每個點所染的顏色決定把每個牌壓入哪個棧。然後模擬即可。
原代碼：
//用圖論的思想來做題
//二分圖著色
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 250
struct
{
int v,next;
}edge[maxn*maxn];
int n;
int stock[maxn], f[maxn];
int head[maxn], ecount, color[maxn], q[maxn];
int out[maxn];
bool ok;
int stk1[maxn], stk2[maxn];
int top1, top2, step;
inline int min(int a,int b){ return a<b?a:b; }
void input()
{
for (int i =0; i < n; i++)
{
scanf("%d", &stock[i]);
out[i] = stock[i];
}
}
void addedge(int&a, int&b)
{
edge[ecount].next = head[a];
edge[ecount].v = b;
head[a] = ecount++;
}
void bfs(int&s)
{
int front =0;
int rear =1;
q[0] = s;
color[s] =1;
while (front != rear)
{
int a = q[front++];
for (int i = head[a]; i !=-1; i = edge[i].next)
{
int b = edge[i].v;
if (!color[b])
{
q[rear++] = b;
color[b] =3- color[a];
}
else if (color[a] == color[b])
{
ok =false;
return;
}
}
}
}
void make(int i)
{
int a = stock[i];
bool did =true;
while (did)
{
did =false;
if (top1 >0&& stk1[top1 -1] ==out[step])
{
top1--;
printf("pop 1\n");
step++;
did =true;
}
if (top2 >0&& stk2[top2 -1] ==out[step])
{
top2--;
printf("pop 2\n");
step++;
did =true;
}
}
if (i <0)
return;
if (color[i] ==1)
{
stk1[top1++] = a;
printf("push 1\n");
}
else
{
stk2[top2++] = a;
printf("push 2\n");
}
}
void print()
{
top1 = top2 =0;
step =0;
for (int i = n -1; i >=0; i--)
make(i);
make(-1);
}
void work()
{
memset(head, -1, sizeof(head));
f[0] = stock[0];
int i;
for (i =1; i < n; i++)
f[i] = min(f[i -1], stock[i]);
ecount =0;
for (i =1; i < n -1; i++)
{
for (int j = i +1; j < n; j++)
{
if (stock[j] >= stock[i])
continue;
if (stock[j] > f[i -1])
{
addedge(i, j);
addedge(j, i);
}
}
}
ok =true;
memset(color, 0, sizeof(color));
for (i =0; i < n; i++)
{
if (!color[i])
bfs(i);
if (!ok)
{
printf("impossible\n");
return;
}
}
print();
}
int main()
{
//freopen("t.txt", "r", stdin);
int t =0;
while (scanf("%d", &n), n)
{
t++;
printf("#%d\n", t);
input();
sort(out, out+ n);
work();
}
return 0;
}
不知道哪裏出錯的代碼。。：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 250
using namespace std;
struct
{
int v,next;
}edge[MAXN*MAXN]; //待連線的邊
//輸入的原數組是a[]，排序後數組是b[]
int a[MAXN],b[MAXN];
int N; // 1 <= N <= 208
int f[MAXN]; //存放前i個輸入中的最小值，判斷能不能在一個棧中使用
int head[MAXN], ecount, color[MAXN], q[MAXN];
bool ok;
int stk1[MAXN], stk2[MAXN];
int top1, top2, step;
inline int min(int a,int b){ return a<b?a:b; }
//addedge
void addedge(int&a, int&b)
{
//其實用一個二維數組會更容易
edge[ecount].next = head[a];
edge[ecount].v = b;
head[a] = ecount++;
}
//bfs
void bfs(int&s)
{
int front =0;
int rear =1;
q[0] = s;
color[s] =1;
while (front != rear)
{
int d = q[front++];
for (int i = head[d]; i !=-1; i = edge[i].next)
{
int c = edge[i].v;
if (!color[c])
{
q[rear++] = c;
color[c] =3- color[d];
}
else if (color[d] == color[c])
{
ok =false;
return;
}
}
}
}
//make
void make(int i)
{
int temp = a[i];
bool did =true;
while (did)
{
did =false;
if (top1 >0&& stk1[top1 -1] ==b[step])
{
top1--;
printf("pop 1\n");
step++;
did =true;
}
if (top2 >0&& stk2[top2 -1] ==b[step])
{
top2--;
printf("pop 2\n");
step++;
did =true;
}
}
if (i <0)
return;
if (color[i] ==1)
{
stk1[top1++] = temp;
printf("push 1\n");
}
else
{
stk2[top2++] = temp;
printf("push 2\n");
}
}
//print
void print()
{
top1 = top2 =0;
step =0;
for (int i = N-1; i >=0; i--)
make(i);
make(-1);
}
//work
void work()
{
memset(head, -1, sizeof(head));
f[0]=a[0];
int i;
//f[i]中存的相當於是前i次中最小的數
for (i =1; i < N; i++)
f[i] = min(f[i -1], a[i]);
//連邊
ecount =0; //邊數
for (i =1; i < N -1; i++)
{
for (int j = i +1; j < N; j++)
{
if (a[j] >= a[i])
continue;
//如果上一個 if 中a[j]<a[i]，這裏又大於前[i-1]個輸入中的最小值
//證明有[i-1]中的某個k，j>i>k時，有a[k]<a[j]<a[i]
//入棧順序是j,i,k
if (a[j] > f[i -1])
{
addedge(i, j);
addedge(j, i);
}
}
}
ok=true;
memset(color, 0, sizeof(color));
for (i =0; i < N; i++)
{
if (!color[i])
bfs(i);
if (!ok)
{
printf("impossible\n");
return;
}
}
print();
}
int main()
{
int i;
int t=0;
while(~scanf("%d",&N) && N!=0)
{
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
printf("#%d\n", ++t);
//排序b[]
sort(b,b+N);
work();
}
return 0;
}
最後更新：2017-04-03 05:39:41