2009年12月12日 星期六

UVa 200 Rare Order

200    Rare Order    poao899    Accepted    C++    0.012    2009-12-12 11:28:09                            .


不難不過覺得好有趣(?

寫過太多奇怪的算法好久沒有好好想一題了雖然這是我的問題XD

算是...最短路...吧



找出相鄰兩列可以知道的大小關係

再去建圖

//*********************

//UVa 200
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 100000
struct alpha{
    int cha,rank,in,out;
    bool operator<(const alpha &b)const{
        return rank<b.rank;
    }
}A[30];
int dist[30][30],nlen,plen,st,cnt;
char S1[30],S2[30];
main(){
    char *now=S1,*pre=S2,*t;
    //Initialize
    for(int i=0;i<30;i++){
        A[i].cha='A'+i;
        for(int j=0;j<30;j++)
            dist[i][j]=INF;
    }
    //Input
    while(1){
        gets(now);
        if(now[0]=='#')break;
        nlen=strlen(now);
        for(int i=0;i<nlen&&i<plen;i++)
            if(now[i]!=pre[i]){
                dist[pre[i]-'A'][now[i]-'A']=-1;
                A[now[i]-'A'].in++;
                A[pre[i]-'A'].out++;
                break;
            }
        plen=nlen;
        t=now;now=pre;pre=t;
    }
    //Find Start
    for(int i=0;i<30;i++){
        if(A[i].in+A[i].out >0 && A[i].in==0){
            st=i;
            break;
        }
    }
    dist[st][st]=0;
    //Floyd-Warshall
    for(int k=0;k<30;k++)
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                if(dist[i][k]+dist[k][j] < dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    //Rank
    for(int i=0;i<30;i++){
        if(dist[st][i]<=0)
            A[i].rank=-dist[st][i];
        else A[i].rank=10000;
    }
    //Sort
    std::sort(A,A+30);
    //Output
    for(int i=0;i<30;i++){
        if(A[i].rank==10000)break;
        printf("%c",A[i].cha);
    }
    printf("\n");
}


2009年12月11日 星期五

UVa 11045 My T-shirt suits me [Flow]

11045    My T-shirt suit...    poao899    Accepted    C++    0.020    2009-12-12 05:59:59                      .


花了半小時co

不過少打一個括號debug半小時= =


是說  同TIOJ 1469 制服發放問題

不過貌似有其他解法= =看TIOJ大家的速度...還有code length

應該是有辦法greedy?

//******************************

//13:04 - 13:31
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 100000
struct arc{
    int j,con;
    arc *topair,*next;
    void set(int to,int c,arc *t,arc *n){
        j=to;con=c;
        topair=t;next=n;
    }
}A[MAX],*N[MAX],*from[MAX];
int arr[INF],t;
struct queue{
    int front,rear,*ar;
    void init(){
        front=rear=0;
        ar=arr;
    }
    int deq(){
        int a=ar[front];
        front=++front%INF;
        return a;
    }
    void enq(int a){
        ar[rear]=a;
        rear=++rear%INF;
    }
}q;
int arcCnt,n,m,max,fa[MAX];
char s[10];
arc* get(){
    return A+arcCnt++;
}
void build(int i,int j,int c){
    arc *p=get(),*q=get(),*r;
    r=N[i];
    N[i]=p;
    p->set(j,c,q,r);
    r=N[j];
    N[j]=q;
    q->set(i,0,p,r);
}
/*
S 0
T MAX-1
size
XXL - XS    201 - 206
*/
main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d\n",&n,&m);
        //Initialize
        arcCnt=max=0;
        for(int i=0;i<MAX;i++){
            A[i].topair=A[i].next=N[i]=NULL;
        }
        // S & T
        n/=6;
        for(int i=201;i<207;i++)
            build(0,i,n);
        //Input
        for(int i=1;i<=m;i++){
            int toSet;
            for(int j=0;j<2;j++){
                scanf("%s",s);
                if(s[0]=='X'){
                    if(s[1]=='X')
                        toSet=201;
                    else if(s[1]=='L')
                        toSet=202;
                    else if(s[1]=='S')
                        toSet=206;
                }
                else{
                    switch(s[0]){
                        case'L':
                            toSet=203;
                            break;
                        case'M':
                            toSet=204;
                            break;
                        case'S':
                            toSet=205;
                            break;
                    }
                }
                build(toSet,i,1);
            }
            build(i,999,1);
        }
        //Max-Flow
        while(1){
            int flow=INF;
            //Initialize
            for(int i=0;i<MAX;i++){
                fa[i]=-1;
                from[i]=NULL;
            }
            q.init();
            q.enq(0);
            //BFS
            while(q.front!=q.rear){
                int now=q.deq();
                for(arc *p=N[now];p;p=p->next){
                    if(p->con > 0 && fa[p->j]==-1){
                        q.enq(p->j);
                        fa[p->j]=now;
                        from[p->j]=p;
                    }
                }
            }
            if(fa[999]==-1)break;
            //flow
            for(int now=999;now;now=fa[now]){
                if(flow>from[now]->con)
                    flow=from[now]->con;
            }
            if(!flow)break;
            for(int now=999;now;now=fa[now]){
                from[now]->con-=flow;
                from[now]->topair->con+=flow;
            }
            max+=flow;
        }
        puts(max==m?"YES":"NO");
    }
}


UVa 567 Risk [Shortest Path]

567    Risk    poao899    Accepted    C++    0.084    2009-12-11 15:33:06                          .

昨天看題目看了十幾分鐘竟然是無腦題=口=


20個點沒有權重的最短路orz

//********************************

#include<stdio.h>
#define INF 1000000
int dist[30][30],cnt,a,b,n;
main(){
    for(int z=1;~scanf("%d",&cnt);z++){
        printf("Test Set #%d\n",z);
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                dist[i][j]=i==j?0:INF;
        for(int i=1;i<20;i++){
            while(cnt-->0){
                scanf("%d",&n);
                dist[i][n]=dist[n][i]=1;
            }
            scanf("%d",&cnt);
        }
        //Floyd –Warshall
        for(int k=1;k<=20;k++)
            for(int i=1;i<=20;i++)
                for(int j=1;j<=20;j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k]+dist[k][j];
        for(int i=0;i<cnt;i++){
            scanf("%d%d",&a,&b);
            printf("%2d to %2d:%2d\n",a,b,dist[a][b]);
        }
        puts("");
    }
}


TIOJ 1174 The Shortest Distance

nolonger    896K    478MS    G++     0.29K     2009-12-11 16:03:17                              .

唔很像Mearge Sort的作法...


排序後O(n)

//************************

#include<algo.h>
int a[200000],b[200000],n,m,z;
main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",a+i);
for(int i=0;i<m;i++)
scanf("%d",b+i);
sort(a,a+n);
sort(b,b+m);
z=1<<31-1;
for(int i=0,j=0;i<n&&j<m;a[i]>b[j]?j++:i++)
z<?=abs(a[i]-b[j]);
printf("%d\n",z);
}


TIOJ 1061 井字遊戲(TTT) [ 95北市賽 ] [DFS]

poao899    0K    167MS    G++     0.84K     2009-12-11 15:29:25                                           .

DFS + Hash判重(咦好像不是這樣用

是說co了四次QQ

有兩次在DFS時不printf()會跑不起來超詭異



//*****************************

#include<stdio.h>
short way[8][3]={
    0,1,2,
    3,4,5,
    6,7,8,
    0,3,6,
    1,4,7,
    2,5,8,
    0,4,8,
    2,4,6,
};
short n,st,cnt[3],a[10],o,x,c;
bool H[19683];
bool hash(){
    int h=0;
    for(int i=0;i<9;i++)
        h=h*3+a[i];
    if(H[h])return 1;
    H[h]=1;return 0;
}
int chk(){
    short x;
    for(int i=0;i<8;i++)
        if((x=a[way[i][0]]) == a[way[i][1]] && a[way[i][1]] == a[way[i][2]] && x)
            return x;
    return 0;
}
void dfs(bool pl){
    int b=0,x=chk();
    if(x){
        if(!hash())
            cnt[x]++;
        return;
    }
    for(int i=0;i<9;i++){
        if(a[i]==0){
            a[i]=pl+1;
            dfs(!pl);
            a[i]=0;
            b=1;
        }
    }
    if(!b && !hash())
        cnt[x]++;
}

main(){
    for(int z=0;z<9;z++){
        c=getchar();
        if(c=='O'){o++;a[z]=1;}
        else if(c=='X'){x++;a[z]=2;}
        else a[z]=0;
    }
    dfs(o>x);
    printf("%hd %hd %hd %hd\n",cnt[0]+cnt[1]+cnt[2],cnt[1],cnt[2],cnt[0]);
}


TIOJ 1042 E.老問題 [ NPSC2003初賽 ] [Flow]

poao899    716K    140MS    G++     1.94K     2009-12-11 11:59:34                             .


Minimum-Cost Maximum Flow.

第一題最小花費最大流>//<

是說相鄰矩陣比相鄰串列好寫多了


一開始WA得莫名重co一次就過了= =

//**************************

#include<stdio.h>
#define MAX 2147483647
#define NODE 300
#define QLEN 1000000
int con[NODE][NODE],cost[NODE][NODE],dist[NODE],from[NODE];
bool inq[NODE];
int arr[QLEN];
struct queue{
    int front,rear,*ar;
    void init(){
        front=rear=0;
        ar=arr;
    }
    int deq(){
        int x=ar[front];
        front=++front%QLEN;
        return x;
    }
    void enq(int a){
        ar[rear]=a;
        rear=++rear%QLEN;
    }
}q;
int n,t,max;
main(){
    while(scanf("%d",&n),n){
        //Initialize
        max=0;
        for(int i=0;i<NODE;i++)
            for(int j=0;j<NODE;j++)
                con[i][j]=cost[i][j]=0;
        for(int i=1;i<=n;i++)
            con[0][i]=con[i+150][NODE-1]=1;
        //Input
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                scanf("%d",&t);
                con[i][j+150]=1;
                cost[i][j+150]=-t;
                cost[j+150][i]=t;
                if(!t)con[i][j+150]=1;
            }
        while(1){
            //Initialize
            q.init();q.enq(0);
            int flow=MAX,now,m=0;
            for(int i=0;i<NODE;i++){
                dist[i]=MAX;inq[i]=0;
                from[i]=-1;
            }
            //SPFA
            dist[0]=0;inq[0]=1;
            while(q.front!=q.rear){
                now=q.deq();
                for(int i=0;i<=NODE;i++){
                    if(con[now][i]>0 && dist[i]>dist[now]+cost[now][i]){
                        dist[i]=dist[now]+cost[now][i];
                        from[i]=now;
                        if(!inq[i]){
                            inq[i]=1;
                            q.enq(i);
                        }
                    }
                }
                inq[now]=0;
            }
            if(from[NODE-1] == -1)break;
            for(now=NODE-1;now;now=from[now]){
                if(flow>con[from[now]][now])
                    flow=con[from[now]][now];
            }
            for(now=NODE-1;now;now=from[now]){
                m+=cost[from[now]][now];
                con[from[now]][now]-=flow;
                con[now][from[now]]+=flow;
            }
            if(m<=0)
                max+=m;
        }
        printf("%d\n",-max);
    }
}


2009年12月10日 星期四

TIOJ 1236 工廠生產問題 [ TOI 2006 ] [Flow]

poao899    184K    289MS    G++     1.62K     2009-12-10 16:13:52                                   .

一樣是Flow =w=


唔MAX一開始調10^9會WA

哪家工廠生產這麼有效率啦(翻桌


是說這題要拆點、沒給測資範圍

然後就沒什麼特別了(?


//****************************

#include<stdio.h>
#define QLEN 1000100
#define MAX 2147483647
#define NMAX 1000
struct arc{
int j,con;
arc *next,*topair;
void set(int to,int c,arc* n,arc* t){
j=to;con=c;
next=n;topair=t;
}
}A[1000000],*N[NMAX],*from[NMAX];
int que[QLEN];
struct queue{
int front,rear;
int *ar;
void init(){
ar=que;
front=rear=0;
}
void enq(int a){
ar[rear]=a;
rear=++rear%QLEN;
}
int deq(){
int x=ar[front];
front=++front%QLEN;
return x;
}
}q;
arc* get(){
static int cnt=0;
return A+cnt++;
}
void build(int i,int j,int con){
arc *p=get(),*q=get(),*r;
r=N[i];
N[i]=p;
p->set(j,con,r,q);
r=N[j];
N[j]=q;
q->set(i,0,r,p);
}
int n,m,a,b,f,max,indeg[NMAX],outdeg[NMAX],fa[NMAX],c;
int bfs(){
for(int i=0;i<NMAX;i++)
fa[i]=-1;
q.init();
q.enq(0);
int flow=MAX;
while(q.front!=q.rear){
int now=q.deq();
for(arc *p=N[now];p;p=p->next){
if(fa[p->j]==-1 && p->con > 0){
q.enq(p->j);
fa[p->j]=now;
from[p->j]=p;
if(flow > p->con)
flow=p->con;
}
}
}
if(fa[999]==-1)return 0;
return flow;
}
void resi(int flow){
for(int now=999;now;now=fa[now]){
from[now]->con-=flow;
from[now]->topair->con+=flow;
}
}
main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&c);
build(i,i+500,c);
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
build(a+500,b,MAX);
indeg[b]++;
outdeg[a]++;
}
for(int i=1;i<=n;i++){
if(!indeg[i])
build(0,i,MAX);
if(!outdeg[i])
build(i+500,999,MAX);
}
while(1){
f=bfs();
if(!f)break;
resi(f);
max+=f;
}
printf("%d\n",max);
}