顯示具有 待AC 標籤的文章。 顯示所有文章
顯示具有 待AC 標籤的文章。 顯示所有文章

2011年6月20日 星期一

UVa 506 System Dependencies

,

,

,

,

,



Link






===簡單的翻譯(不逐字翻了...字好多)



安裝軟體有很多依存關係,例如說你沒有TCPIP你就裝不起來TELNET。



所以如果明確(explicity)要裝TELNET,你會附帶地把TCPIP裝起來。

等你下次裝FTP(也需要TCPIP)時,就不用重裝一遍TCPIP。

但同樣的,在TELNET還裝著的情況下你不能把TCPIP移除。



有時候我們需要移除一些程式。為了省出更多空間,我們在移除某些程式時會把一些

只為了這個程式能正常運行才附帶安裝的檔案一起移除。

例如說如果我們為了裝TELNET而把TCPIP附帶裝起來,之後我們移除TELNET時發現,

TCPIP只是為了讓TELNET能正常運作而附帶安裝,TELNET移除後TCPIP將沒有存在的必要

便會順便將TCPIP解除安裝。



已經裝上的軟體不會再被安裝一遍(因為附帶而安裝的軟體不會因為再被安裝一遍而

變成明確要安裝的軟體)、已經移除的軟體也不能再被移除。



===



寫這題用到一堆C++的技巧xD



#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <sstream>

#include <list>

#include <vector>

#include <string>

#include <map>



#define MAX 2510



//Converter

std::map<std::string, int> conv;

std::string rconv[MAX];

int ccnt;

//Answer List

std::list<int> ans;

std::list<int>::iterator it;

//Graph

std::vector<int> re[MAX], ee[MAX];

//DAG DP

int chneed[MAX], vst[MAX], ins[MAX], im[MAX];

//Parser

std::stringstream sin;

std::string buf;



inline int getno(std::string&b) {

 int rtn = conv[b];

 if(rtn == 0) {

  ccnt ++;

  conv[b] = ccnt;

  rconv[ccnt] = b;

  rtn = ccnt;

 }

 return rtn;

}



inline void insert(int np) {

 ans.push_back(np);

 ins[np] = true;

 std::cout << "   Installing " << rconv[np] << '\n';

}



void dfsI(int now) {

 chneed[now] ++;

 vst[now] ++;

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsI(nxt);

 }

 if(!ins[now]) {

  ins[now] = true;

  insert(now);

 }

}



inline void remove(int np) {

 ans.remove(np);

 ins[np] = im[np] = false;

 std::cout << "   Removing " << rconv[np] << '\n';

}



void dfsR1(int now, int need) {

 vst[now] = true;

 chneed[now] -= need;

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(vst[nxt]) continue;

  dfsR1(nxt, need);

 }

}



void dfsR2(int now) {

 if(chneed[now]) return;

 int can = true;

 for(int i=ee[now].size()-1,nxt; i>=0; i--) {

  nxt = ee[now][i];

  if(ins[nxt]) {

   can = false;

   break;

  }

 }

 if(!can) return;

 remove(now);

 for(int i=re[now].size()-1,nxt; i>=0; i--) {

  nxt = re[now][i];

  if(!ins[nxt]) continue;

  dfsR2(nxt);

 }

}



int main() {

 while(true) {

  getline(std::cin, buf);

  std::cout << buf << '\n';

  sin.clear();

  sin.str(buf);

  sin >> buf;

  std::string ch, fa;

  int nch, nfa;

  switch(buf[0]) {

   case 'D':

    sin >> ch;

    nch = getno(ch);

    while(sin >> fa) {

     nfa = getno(fa);

     re[nch].push_back(nfa);

     ee[nfa].push_back(nch);

    }

   break;

   case 'I':

    sin >> ch;

    nch = getno(ch);

    if(ins[nch]) {

     std::cout << "   " << ch <<  " is already installed.\n";

    }

    else {

     memset(vst, 0, sizeof(vst));

     im[nch] = true;

     dfsI(nch);

    }

   break;

   case 'R':

    sin >> ch;

    nch = getno(ch);

    if(!ins[nch]) {

     std::cout << "   " << ch << " is not installed.\n";

    }

    else {

     if(chneed[nch]>1 || (chneed[nch]==1 && !im[nch])) {

      std::cout << "   " << ch << " is still needed.\n";

     }

     else {

      memset(vst, 0, sizeof(vst));

      dfsR1(nch, im[nch]);

      dfsR2(nch);

     }

    }

   break;

   case 'L':

    for(it=ans.begin(); it!=ans.end(); it++) {

     std::cout << "   " << rconv[*it] << '\n';

    }

   break;

   case 'E':

    exit(0);

   break;

  }

 }

}

//8966453  506  System Dependencies  Accepted  C++  0.024  2011-06-19 06:57:53



2010年2月28日 星期日

PKU 3345 Bribing FIPA

題目大意:


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

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

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

至少要付出多少價值

0 <=200









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

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


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






2009年11月7日 星期六

UVa 336 A Node Too Far

佛洛伊德為什麼會WA  QQ                                                                                                                    .


這樣會讓我對佛洛伊德產生陰影QQ


//UVa 336

#include<stdio.h>
int dist[31][31];
int count[31][32];
int convert[31],ccnt=1;
int n,cnt=1,i,j;
int find(int key){
    for(int i=0;i<ccnt;i++)
        if(key==convert[i])
            return i;
    return -1;
}
main(){
    freopen("UVa336.in","r",stdin);
    freopen("UVa336.out","w",stdout);
    while(scanf("%d",&n),n){
        //Initialize
        ccnt=1;
        for(int i=0;i<31;i++)
            for(int j=0;j<31;j++){
                dist[i][j]=i==j?0:20000;
                count[i][j]=0;
            }
        //Input
        while(n--){
            int i,j;
            scanf("%d%d",&i,&j);
            int fi=find(i),fj=find(j);
            if(fi==-1)convert[ccnt++]=i;
            if(fj==-1)convert[ccnt++]=j;
            fi=find(i);
            fj=find(j);
            dist[fi][fj]=dist[fj][fi]=1;
        }
        //Floyd-Warshall
        for(int k=1;k<ccnt;k++)
            for(int i=1;i<ccnt;i++)
                for(int j=1;j<ccnt;j++)
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                        dist[i][j]=dist[i][k]+dist[k][j];
        //Count The Dist
        for(int i=1;i<ccnt;i++){
            for(int j=1;j<ccnt;j++){
                //printf("dist %d %d:%d\n",i,j,dist[i][j]);
                if(dist[i][j]<31)
                    count[i][dist[i][j]]++;
            }
            for(int j=1;j<31;j++)
                count[i][j]+=count[i][j-1];
        }
        //Output
        while(1){
            int i,j,fi;
            scanf("%d%d",&i,&j);
            if(i==j&&!j)break;
            if(j>30)j=30;
            fi=find(i);
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cnt++,ccnt-1-count[find(i)][j],i,j);
        }
    }
}