PKU 3345 Bribing FIPA

題目大意：


給你一個森林，每個點都有價值

如果你付出那個點的價值就可以得到他和他所有的子孫節點

然後我有n個節點、希望至少能得到其中m個

至少要付出多少價值

0 <=200









=========是雷  嗎?=========

看起來可以O(n^3)DP


不過這個輸入好不可愛=口=

UVa 10102 The path in the colored field

7772863      10102      The path in the...      poao899      Accepted      C++      0.864      2010-02-23 14:56:10                                           .


題目意義有一點點不好懂囧

看了好久好久



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

#include<stdio.h>
#define QLEN 20000
int map[100][100],step[100][100],m,max,min;
char input[110];
struct queue{
    int front,rear,a[QLEN][2];
    void init(){
        front=0;
        rear=0;
    }
    void push(int x,int y,int dep){
        if(x>=0&&x<m&&y>=0&&y<m&&step[x][y]==0){
            //printf("push %d %d:%d\n",x,y,dep);
            step[x][y]=dep;
            a[rear][0]=x;
            a[rear][1]=y;
            if(map[x][y]==3 && min>dep){
                min=dep;
            }
            rear=++rear%QLEN;
        }
    }
    bool pop(){
        if(front==rear)return 0;
        int x=a[front][0],y=a[front][1],d=step[x][y]+1;
        push(x+1,y,d);
        push(x-1,y,d);
        push(x,y+1,d);
        push(x,y-1,d);
        front=++front%QLEN;
        return 1;
    }
}q;
int main(){
    while(~scanf("%d\n",&m)){
        //Init
        max=-1;
        //Input
        for(int i=0;i<m;i++){
            gets(input);
            for(int j=0;j<m;j++){
                map[i][j]=input[j]-'0';
            }
        }
        //BFS & Count
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                if(map[i][j]==1){
                    min=2147483647;
                    for(int i=0;i<m;i++)
                        for(int j=0;j<m;j++)
                            step[i][j]=0;
                    //printf("start: %d %d\n",i,j);
                    q.init();
                    q.push(i,j,1);
                    //puts("BFS");
                    while(q.pop());
                    //printf("min%d\n",min);
                    if(max<min)max=min;
                }
        //Output
        printf("%d\n",max-1);
    }
}

UVa 10583 Ubiquitous Religions

7772759      10583      Ubiquitous Reli...      poao899      Accepted      C++      0.152      2010-02-23 13:53:33                                          .


看到Lucky Cat上面分類是少見的disjoint set就來寫了

唔竟然是空虛題orz



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

#include<stdio.h>
#define MAX 50010
int root[MAX],caseCnt,cnt,n,m,a,b;
bool used[MAX];
int find(int a){
    return a==root[a]?a:root[a]=find(root[a]);
}
int main(){
    while(scanf("%d%d",&n,&m),n,m){
        //Init
        for(int i=1;i<=n;i++){
            root[i]=i;
            used[i]=0;
        }
        cnt=0;
        //Input
        while(m--){
            scanf("%d%d",&a,&b);
            root[find(a)]=find(b);
        }
        //Count
        for(int i=1;i<=n;i++)
            if(!used[find(i)]){
                used[root[i]]=1;
                cnt++;
            }
        //Output
        printf("Case %d: %d\n",++caseCnt,cnt);
    }
}

UVa 10354 Problem B - Avoiding Your Boss [Graph]

7760819      10354      Avoiding Your Boss      poao899      Accepted      C++      0.040      2010-02-17 13:09:02                                               .


唔  簡單來說

一張無向有權圖

找到TH <-> M 的最短路徑

但不能經過BH <-> OF任何一條最短路徑的任一節點







反正會在最短路徑上的點就表示dist[bh][i]+dist[i][of] = dist[bh][of]嘛ˇ







#include<stdio.h>
#define MAX 1000000000

int dist[110][110],d2[110][110];
int p,r,bh,of,th,m,p1,p2,d,ti,tj,tk;
bool can[110];

main(){
    while(~scanf("%d%d%d%d%d%d",&p,&r,&bh,&of,&th,&m)){
        //Init
        for(int i=0;i<110;i++){
            for(int j=0;j<110;j++){
                dist[i][j]=d2[i][j]=MAX;
            }
            dist[i][i]=d2[i][i]=0;
            can[i]=1;
        }

        //Input E
        while(r--){
            scanf("%d%d%d",&p1,&p2,&d);
            dist[p1][p2]=d2[p1][p2]=dist[p2][p1]=d2[p2][p1]=d;
        }

        //First Warshall : Find BH <-> OF

        for(int k=0;k<=p;k++)
            for(int i=0;i<=p;i++)
                for(int j=0;j<=p;j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                        dist[i][j]=dist[i][k]+dist[k][j];

            //Find Nodes Which Would Be Visited By Boss

        for(int i=0;i<=p;i++)
            if(dist[bh][i]+dist[i][of] == dist[bh][of])
                can[i]=0;


        //Second Warshall : Find TH <-> M

        for(int k=0;k<=p;k++)
            if(can[k])
                for(int i=0;i<=p;i++)
                    if(can[i])
                        for(int j=0;j<=p;j++)
                            if(can[j])
                                if(d2[i][k]+d2[k][j] < d2[i][j])
                                    d2[i][j]=d2[i][k]+d2[k][j];

        //Output

        if(d2[th][m]==MAX || !can[th] || !can[m])
            puts("MISSION IMPOSSIBLE.");
        else printf("%d\n",d2[th][m]);
    }
}

UVa 10355 Problem C - Superman [CG]

10355      Superman      poao899      Accepted      C++      0.012      2010-02-16 09:54:03                                              .


嗯  兩個月沒coding了

為什麼第一個挑的題目就是計算幾何啦囧

是說不難  但是co得亂七八糟


#include<stdio.h>
#include<math.h>
#include<algorithm>
char name[20];
struct point{
    double x,y,z;
    void get(){
        scanf("%lf%lf%lf\n",&x,&y,&z);
    }
}st,ed,cen,p;
double t;
int r,n;
inline double pow2(double a){
    return a*a;
}
inline double dist2(point a,point b){
    return pow2(a.x-b.x)+pow2(a.y-b.y)+pow2(a.z-b.z);
}
struct node{
    double x;
    int flag;
    bool operator<(const node &b)const{
        return x<b.x || x==b.x&&flag>b.flag;
    }
};
struct line{
    node N[30];
    int cnt;
    void init(){
        cnt=0;
    }
    void push(double a,double b){
        if(a<0)a=0;
        if(b>1)b=1;
        N[cnt].x=a;
        N[cnt++].flag=1;
        N[cnt].x=b;
        N[cnt++].flag=-1;
    }
}L;
int main(){
    while(~scanf("%s",name)){
        puts(name);
        L.init();
        st.get();
        ed.get();
        scanf("%d",&n);
        double xt,yt,zt,c,dis,dt;
        xt=ed.x-st.x;
        yt=ed.y-st.y;
        zt=ed.z-st.z;
        while(n--){
            cen.get();
            scanf("%d",&r);
            c=xt*cen.x + yt*cen.y + zt*cen.z;
            t = (c -xt*st.x -yt*st.y -zt*st.z)/(pow2(xt)+pow2(yt)+pow2(zt));
            p.x=xt*t + st.x;
            p.y=yt*t + st.y;
            p.z=zt*t + st.z;
            dis = pow2(double(r)) - dist2(cen,p);
            if(dis<0)continue;
            dt = sqrt((dis)/(pow2(xt)+pow2(yt)+pow2(zt)));
            L.push(t-dt,t+dt);
        }
        int cnt=0;double pre=0,total=0;
        std::sort(L.N,L.N+L.cnt);
        for(int i=0;i<L.cnt;i++){
            if(cnt>0){
                total+=(L.N[i].x-pre);
            }
            cnt+=L.N[i].flag;
            pre=L.N[i].x;
        }
        printf("%.2lf\n",total*100);
    }
    return 0;
}