,
,
,
,
,
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
2011年6月20日 星期一
2010年2月28日 星期日
PKU 3345 Bribing FIPA
題目大意:
給你一個森林,每個點都有價值
如果你付出那個點的價值就可以得到他和他所有的子孫節點
然後我有n個節點、希望至少能得到其中m個
至少要付出多少價值
0 <=200
=========是雷 嗎?=========
看起來可以O(n^3)DP
不過這個輸入好不可愛=口=
給你一個森林,每個點都有價值
如果你付出那個點的價值就可以得到他和他所有的子孫節點
然後我有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);
}
}
}
這樣會讓我對佛洛伊德產生陰影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);
}
}
}
訂閱:
文章 (Atom)