「AOJ1011～1020」の編集履歴（バックアップ）一覧はこちら
AOJ1011～1020 - (2011/11/12 (土) 16:03:19) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*1014 Computation of Minimum Length of Pipeline
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014
源泉から都市へパイプラインを引く問題。
都市間の距離、源泉から都市への距離が与えれるので最小の距離でパイプを接続せよという問題。
解法
どの源泉も供給能力は同じで区別がつきません。
源泉を全て丸で囲んで１点とみなし、源泉から都市への最小距離を最初に更新します。
後は都市と源泉を点とみなしグラフの上でプリム法で接続していくだけです。
#include<stdio.h>
#include<queue>
#include<string.h>
#include <algorithm>
int map[102][102];//0が源泉ひとまとめ、1以降が都市
struct Edge{
int to,len;//エッジの接続先と繋げるパイプの長さ
bool operator<(const Edge& e)const{
return e.len<len;
}
};
const int stop=0;
int prim(int d){
//プリム法でパイプラインの配置を解く。
//まず源泉は全て長さ0の辺でつながっているという過程で始める
std::priority_queue<Edge> qu;
bool conOKs[101];
memset(conOKs,true,sizeof(conOKs));
Edge edge;
edge.len=0;
edge.to=0;
qu.push(edge);//最初長さ0で源泉に接続する
int nextP,sumLen=0,count=0;//
while(!qu.empty()){
edge=qu.top();//一番短いパイプラインを選んでいく
qu.pop();
nextP=edge.to;
if(conOKs[nextP]==false) continue;//接続済みの都市にパイプラインをつなげようとした
conOKs[nextP]=false;
count++;//つなげた都市の数
sumLen+=edge.len;//答えの集計
if(count==d+1) break;//全ての都市と源泉をつないだら終了
for(int i=0;i<=d;i++){
if(conOKs[i]==false||map[nextP][i]==stop)continue;//もうパイプを通した都市もしくは接続不能の都市への接続は無視する
edge.to =i;
edge.len=map[nextP][i];
qu.push(edge);
}
}
return sumLen;
}
void setData(int s,int d){
int temp;
memset(map,stop,sizeof(map));
for(int i=0;i<s;i++){
for(int j=1;j<=d;j++){
scanf("%d",&temp);
if(map[0][j]==0 || (map[0][j]>temp&&temp!=stop)){
map[0][j]=temp;//全ての源泉を丸で囲んで１点とみなす
}
map[j][0]=map[0][j];
}
}
for(int i=1;i<d;i++){
for(int j=i+1;j<=d;j++){
scanf("%d",&map[i][j]);//都市間の距離のセット
map[j][i]=map[i][j];
}
}
printf("%d\n",prim(d));
}
int main(){
int s,d;
while(1){
scanf("%d %d",&s,&d);
if(s==0 && d==0) break;
setData(s,d);
}
}
----
*1015 Dominating Set
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1015
最小の頂点支配集合を求める問題。
解法
初めはBitSetで解こうかと考えたのですが、最大頂点数が分からなかった(多分書いてない？)のでvectorに頂点支配されるかの状態を保存することにしました。
コードは深さ優先探索である点を頂点支配集合に入れる入れないを２分探索しているだけです。
素朴な方法で速度が出なかったので小手先のテクニックを入れたらコードが膨らみました。
深さ優先探索するまえに辺の多い点を優先して調べるよう並べ替えること。
もう一つはある点で支配できる領域が他の点で支配できる領域のサブセットをなすならその点は探索で無視する。
残りは探索の途中で残りの点をすべて使っても頂点支配出来ない点が判明した時探索を枝が利すること。
ということをしています。
小手先すぎて駄目ですね、20倍程度しか速くなりませんでした。
頂点支配集合についてきちんと勉強することにしようと考えた問題でした。
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <map>
#include <set>
struct vecSizeSorter
{
bool operator()( const std::vector<int>& lhs, const std::vector<int>& rhs ) const
{
return lhs.size() > rhs.size();//点に入る辺の本数が多い方を優先
}
};
//グローバル変数まとめ
int ans,x;
std::vector<std::vector<int> > map;//グラフのつながり
std::vector<bool> subSet;//ある点で支配される領域が別の点のサブセットでないかのチェック
std::vector<std::set<int> > cut;
//グローバル変数終わり
void saiki(std::vector<bool> state,int p,int count,int vCount){
if(ans<=vCount) return;
//支配集合に入ってる数が全体になった
if(count==x){
ans=ans>vCount?vCount:ans;
return;
}
if(p>=x)return;
if(subSet[p]==true){
saiki(state,p+1,count,vCount);//この点Pは他の点のサブセットなので無視する
return ;
}
for(int i=0;i<x;i++){
if(state[i]==false && cut[p].find(i)==cut[p].end()){
//残りの点では被覆できないことが判明したのでリターン
return ;
}
}
int backCount=count;
std::vector<bool> back=state;
//この点ｐを支配集合とする
for(int i=0;i<map[p].size();i++){
if(state[map[p][i]]==false){
count++;
state[map[p][i]]=true;
}
}
if(backCount!=count){
saiki(state,p+1,count,vCount+1);//支配集合とする
state=back;//変化があったので元に戻す
count=backCount;
}
saiki(state,p+1,count,vCount);//この点を支配集合としない
}
bool isSubSet(std::vector<int>& vec1,std::vector<int>& vec2){
//ソート済みを渡すので必ずvec1>=vec2
//vec2がvec1のサブセットでないかをチェックする
std::set<int> sets;
sets.insert(vec1.begin(),vec1.end());
int count=sets.size();
sets.insert(vec2.begin(),vec2.end());
if(count==sets.size()){
return true;
}else{
return false;
}
}
void search(int x,int y){
std::vector<bool> state;
ans=x+1;
map.clear();
map.resize(x);
state.resize(x);
int from,to;
for(int i=0;i<y;i++){
scanf("%d %d",&from,&to);
map[from].push_back(to);
map[to].push_back(from);
}
for(int i=0;i<x;i++){
map[i].insert(map[i].begin(),i);//支配集合の中心となる点を先頭に挿入
state[i]=false;
}
std::sort(map.begin(),map.end(),vecSizeSorter());//小手先テク頂点集合をソートして辺の多い点から検証する
int p;
std::map<int,int> temp;
for(int i=0;i<x;i++){
temp[map[i][0]]=i;//点の位置が入れ替わったので修正
}
for(int i=0;i<x;i++){
for(int j=0;j<map[i].size();j++){
map[i][j]=temp[map[i][j]];
}
std::sort(map[i].begin(),map[i].end());
}
subSet.clear();
subSet.resize(x);//ある点で頂点支配できる点が他の点の頂点支配のサブセットなら無視する
for(int i=0;i<x;i++)subSet[i]=false;
for(int i=0;i<x-1;i++){
for(int j=i+1;j<x;j++){
if(isSubSet(map[i],map[j])==true){
subSet[j]=true;
}
}
}
//深さ優先探索の途中残りの点で被覆が出来ないことが判明させるためのSet
cut.clear();
cut.resize(x);
cut[x-1].insert(map[x-1].begin(),map[x-1].end());
for(int i=x-2;i>=0;i--){
cut[i].insert(cut[i+1].begin(),cut[i+1].end());
cut[i].insert(map[i].begin(),map[i].end());
}
//深さ優先探索で一つずつ点を頂点集合に含める含めないを試して最小値を求める
saiki(state,0,0,0);
printf("%d\n",ans);
}
int main(){
int y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0) break;
search(x,y);
}
}
----
*1014 Computation of Minimum Length of Pipeline
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014
源泉から都市へパイプラインを引く問題。
都市間の距離、源泉から都市への距離が与えれるので最小の距離でパイプを接続せよという問題。
解法
どの源泉も供給能力は同じで区別がつきません。
源泉を全て丸で囲んで１点とみなし、源泉から都市への最小距離を最初に更新します。
後は都市と源泉を点とみなしグラフの上でプリム法で接続していくだけです。
#include<stdio.h>
#include<queue>
#include<string.h>
#include <algorithm>
int map[102][102];//0が源泉ひとまとめ、1以降が都市
struct Edge{
int to,len;//エッジの接続先と繋げるパイプの長さ
bool operator<(const Edge& e)const{
return e.len<len;
}
};
const int stop=0;
int prim(int d){
//プリム法でパイプラインの配置を解く。
//まず源泉は全て長さ0の辺でつながっているという過程で始める
std::priority_queue<Edge> qu;
bool conOKs[101];
memset(conOKs,true,sizeof(conOKs));
Edge edge;
edge.len=0;
edge.to=0;
qu.push(edge);//最初長さ0で源泉に接続する
int nextP,sumLen=0,count=0;//
while(!qu.empty()){
edge=qu.top();//一番短いパイプラインを選んでいく
qu.pop();
nextP=edge.to;
if(conOKs[nextP]==false) continue;//接続済みの都市にパイプラインをつなげようとした
conOKs[nextP]=false;
count++;//つなげた都市の数
sumLen+=edge.len;//答えの集計
if(count==d+1) break;//全ての都市と源泉をつないだら終了
for(int i=0;i<=d;i++){
if(conOKs[i]==false||map[nextP][i]==stop)continue;//もうパイプを通した都市もしくは接続不能の都市への接続は無視する
edge.to =i;
edge.len=map[nextP][i];
qu.push(edge);
}
}
return sumLen;
}
void setData(int s,int d){
int temp;
memset(map,stop,sizeof(map));
for(int i=0;i<s;i++){
for(int j=1;j<=d;j++){
scanf("%d",&temp);
if(map[0][j]==0 || (map[0][j]>temp&&temp!=stop)){
map[0][j]=temp;//全ての源泉を丸で囲んで１点とみなす
}
map[j][0]=map[0][j];
}
}
for(int i=1;i<d;i++){
for(int j=i+1;j<=d;j++){
scanf("%d",&map[i][j]);//都市間の距離のセット
map[j][i]=map[i][j];
}
}
printf("%d\n",prim(d));
}
int main(){
int s,d;
while(1){
scanf("%d %d",&s,&d);
if(s==0 && d==0) break;
setData(s,d);
}
}
----
*1015 Dominating Set
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1015
最小の頂点支配集合を求める問題。
解法
初めはBitSetで解こうかと考えたのですが、最大頂点数が分からなかった(多分書いてない？)のでvectorに頂点支配されるかの状態を保存することにしました。
コードは深さ優先探索である点を頂点支配集合に入れる入れないを２分探索しているだけです。
素朴な方法で速度が出なかったので小手先のテクニックを入れたらコードが膨らみました。
深さ優先探索するまえに辺の多い点を優先して調べるよう並べ替えること。
もう一つはある点で支配できる領域が他の点で支配できる領域のサブセットをなすならその点は探索で無視する。
残りは探索の途中で残りの点をすべて使っても頂点支配出来ない点が判明した時探索を枝刈すること。
ということをしています。
小手先すぎて駄目ですね、20倍程度しか速くなりませんでした。
頂点支配集合についてきちんと勉強することにしようと考えた問題でした。
#include<stdio.h>
#include<vector>
#include <algorithm>
#include <map>
#include <set>
struct vecSizeSorter
{
bool operator()( const std::vector<int>& lhs, const std::vector<int>& rhs ) const
{
return lhs.size() > rhs.size();//点に入る辺の本数が多い方を優先
}
};
//グローバル変数まとめ
int ans,x;
std::vector<std::vector<int> > map;//グラフのつながり
std::vector<bool> subSet;//ある点で支配される領域が別の点のサブセットでないかのチェック
std::vector<std::set<int> > cut;
//グローバル変数終わり
void saiki(std::vector<bool> state,int p,int count,int vCount){
if(ans<=vCount) return;
//支配集合に入ってる数が全体になった
if(count==x){
ans=ans>vCount?vCount:ans;
return;
}
if(p>=x)return;
if(subSet[p]==true){
saiki(state,p+1,count,vCount);//この点Pは他の点のサブセットなので無視する
return ;
}
for(int i=0;i<x;i++){
if(state[i]==false && cut[p].find(i)==cut[p].end()){
//残りの点では被覆できないことが判明したのでリターン
return ;
}
}
int backCount=count;
std::vector<bool> back=state;
//この点ｐを支配集合とする
for(int i=0;i<map[p].size();i++){
if(state[map[p][i]]==false){
count++;
state[map[p][i]]=true;
}
}
if(backCount!=count){
saiki(state,p+1,count,vCount+1);//支配集合とする
state=back;//変化があったので元に戻す
count=backCount;
}
saiki(state,p+1,count,vCount);//この点を支配集合としない
}
bool isSubSet(std::vector<int>& vec1,std::vector<int>& vec2){
//ソート済みを渡すので必ずvec1>=vec2
//vec2がvec1のサブセットでないかをチェックする
std::set<int> sets;
sets.insert(vec1.begin(),vec1.end());
int count=sets.size();
sets.insert(vec2.begin(),vec2.end());
if(count==sets.size()){
return true;
}else{
return false;
}
}
void search(int x,int y){
std::vector<bool> state;
ans=x+1;
map.clear();
map.resize(x);
state.resize(x);
int from,to;
for(int i=0;i<y;i++){
scanf("%d %d",&from,&to);
map[from].push_back(to);
map[to].push_back(from);
}
for(int i=0;i<x;i++){
map[i].insert(map[i].begin(),i);//支配集合の中心となる点を先頭に挿入
state[i]=false;
}
std::sort(map.begin(),map.end(),vecSizeSorter());//小手先テク頂点集合をソートして辺の多い点から検証する
int p;
std::map<int,int> temp;
for(int i=0;i<x;i++){
temp[map[i][0]]=i;//点の位置が入れ替わったので修正
}
for(int i=0;i<x;i++){
for(int j=0;j<map[i].size();j++){
map[i][j]=temp[map[i][j]];
}
std::sort(map[i].begin(),map[i].end());
}
subSet.clear();
subSet.resize(x);//ある点で頂点支配できる点が他の点の頂点支配のサブセットなら無視する
for(int i=0;i<x;i++)subSet[i]=false;
for(int i=0;i<x-1;i++){
for(int j=i+1;j<x;j++){
if(isSubSet(map[i],map[j])==true){
subSet[j]=true;
}
}
}
//深さ優先探索の途中残りの点で被覆が出来ないことが判明させるためのSet
cut.clear();
cut.resize(x);
cut[x-1].insert(map[x-1].begin(),map[x-1].end());
for(int i=x-2;i>=0;i--){
cut[i].insert(cut[i+1].begin(),cut[i+1].end());
cut[i].insert(map[i].begin(),map[i].end());
}
//深さ優先探索で一つずつ点を頂点集合に含める含めないを試して最小値を求める
saiki(state,0,0,0);
printf("%d\n",ans);
}
int main(){
int y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0) break;
search(x,y);
}
}
