土下座しながら探索中

主に競技プログラミング

UVa 11865 : Stream My Contest

UVa 最小有向全域木 2分探索

問題リンク:http://uva.onlinejudge.org/external/118/11865.html

問題概要：
N個のノードとM本の有向な辺の情報が与えられる。
初期状態ではどのノードも辺でつながれていない。
ノードは０から順にN-1まで番号付けられている。
ノード０からその他の全てのノードに移動できるように辺をはりたい。
ただし、追加した辺の総和は値C以下でなければならない。
更に辺をはるためにはある値xを決めた時、xはその辺のコストy以下でなければならない
そうでないような辺は追加できない
以上の条件を満たすxの最大値を求めよ
できない場合は"streaming not possible."と出力せよ

解法：
２分探索でxの値を決めグラフを構築し、そのグラフのノード０をルートとした
最小有向全域木を作成する
そのコストがC以下かどうかで値を更新する


最小有向全域木ライブラリverify用問題
・UVa 11865
・UVa 11183

コード：

#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
#include<cassert>
#include<cstdio>
#include<queue>
#include<deque>

#define REP(i,s,n) for(int i=s;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX_V 1200

using namespace std;
typedef long long ll;

struct P{
  int x,y;
  P(int x=IINF,int y=IINF):x(x),y(y){}
};

struct Pox{
  int from,to,cost;
  Pox(int from=IINF,int to=IINF,int cost=IINF):from(from),to(to),cost(cost){}
};

struct edge{
  int to,cost;
  edge(int to=IINF,int cost=IINF):to(to),cost(cost){}
  bool operator < (const edge& a)const{ return cost < a.cost; }
};

struct Index{
  int from,to,edge;
  Index(int from=IINF,int to=IINF,int edge=IINF):from(from),to(to),edge(edge){}
  bool operator < (const Index &a)const{
    if(from != a.from)return from < a.from;
    if(to != a.to)return to < a.to;
    return edge < a.edge;
  }
  bool operator == (const Index &a)const{ return (from == a.from && to == a.to && edge == a.edge); }
};

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<edge> ve;
typedef vector<ve>  vve;
int N,M;

//Strongly Connected Componet
class SCC{
public:
  int SCC_V;
  vi SCC_G[MAX_V];
  vi SCC_rG[MAX_V];
  vi SCC_vs;
  bool SCC_used[MAX_V];
  int SCC_cmp[MAX_V];

  SCC(int V):SCC_V(V){ SCC_init(V); }

  void SCC_init(int NN){
    SCC_V = NN;
    rep(i,NN){
      SCC_G[i].clear();
      SCC_rG[i].clear();
    }
  }

  void add_edge(int from,int to){
    SCC_G[from].push_back(to);
    SCC_rG[to].push_back(from);
  }

  void dfs(int v){
    SCC_used[v] = true;
    for(int i=0;i<SCC_G[v].size();i++) if(!SCC_used[SCC_G[v][i]]) dfs(SCC_G[v][i]);
    SCC_vs.push_back(v);
  }

  void rdfs(int v,int k){
    SCC_used[v] = true;
    SCC_cmp[v] = k;
    for(int i=0;i<SCC_rG[v].size();i++) if(!SCC_used[SCC_rG[v][i]]) rdfs(SCC_rG[v][i],k);
  }

  int scc(){
    for(int i=0;i<MAX_V;i++)SCC_used[i] = false;
    SCC_vs.clear();
    for(int v=0;v<SCC_V;v++) if(!SCC_used[v]) dfs(v);
    for(int i=0;i<MAX_V;i++)SCC_used[i] = false;
    int k = 0,cnt;

    for(int i=SCC_vs.size()-1;i>=0;i--){
      cnt = 0;
      if(!SCC_used[SCC_vs[i]])rdfs(SCC_vs[i],k++);
    }
    return k;
  }
};
// --------------------------------------- SCC fin

/***
    V : 現段階でのノードの数 (閉路が圧縮されている場合があるためグラフのサイズとは一致しない)
    root : ルート
    G : グラフ、各階層で辺のコストが違う
    tree : 最小有向全域木
    goup : 自分の属しているグループ
    gused : そのグループに辺がはられたかどうか
    prev : １つ先の階層でつかったノードの情報
***/

bool Error;

void Minimum_Cost_Arborescence_Algorithm(int V,int root,vve G,vve &tree,bool *used,int *group,bool *gused,vector<Index> &prev)
{
  if(Error)return;
  /*
    y[i] := 圧縮されたグラフでのノードiにはいる辺のなかで最小のコストをもつ辺の圧縮されていないグラフでの（どのノードから、どのノードへ、辺の番号）
    sub[i] := ノードiに入ってくる辺の最小値、後でこれをそのノードに入る全ての辺から引く
  */

  Index *y = new Index[V];
  int *sub = new int[V];
  rep(i,V)y[i] = Index(IINF,IINF,IINF),sub[i] = IINF;
  rep(i,G.size()) {
    int from = group[i];	  
    rep(j,G[i].size()) {
      int to = group[G[i][j].to];
      if(to == group[root])continue;//rootに入る辺は無駄でしかないのでカット
      if(from == to)continue;//同じ閉路内なのでカット
      int cost = G[i][j].cost;
      if(y[to] == Index(IINF,IINF,IINF))y[to] = Index(i,G[i][j].to,j);
      else if(G[y[to].from][y[to].edge].cost > cost)y[to] = Index(i,G[i][j].to,j);
    }
  }

  SCC scc(V);
  int ECNT = 0;
  rep(i,V) {
    if(y[i] == Index(IINF,IINF,IINF))continue;//ノードiに入ってくる辺はない
    scc.add_edge(group[y[i].from],i);//ノードiにノードy[i].firstの辺が入る
    sub[i] = G[y[i].from][y[i].edge].cost;
    ECNT++;
  }

  if(ECNT != V-1) {
    Error = true;
    return;
  }

  int nV = scc.scc();

  if(V == nV){//閉路がない
    rep(i,V){
      if(y[i] == Index(IINF,IINF,IINF))continue;
      int from = y[i].from;
      int to = y[i].to;
      if(used[to])continue;
      int e = y[i].edge;
      used[to] = true;
      prev.push_back(y[i]);
      tree[from].push_back(edge(to,e));
    }
    return;
  }

  rep(i,G.size()){
    int from = group[i];
    rep(j,G[i].size()){	  
      int to = group[G[i][j].to];
      if(sub[to] == IINF || from == to)continue;
      G[i][j].cost -= sub[to];
    }
  }

  int *ngroup = new int[(int)G.size()];
  rep(i,G.size())ngroup[i] = scc.SCC_cmp[group[i]];

  Minimum_Cost_Arborescence_Algorithm(nV,root,G,tree,used,&ngroup[0],&gused[0],prev);
  if(Error)return;
  rep(i,G.size())gused[i] = false;

  rep(i,prev.size()){
    int from = prev[i].from;
    int to = prev[i].to;
    gused[group[to]] = true;
    used[to] = true;
  }

  rep(i,V){
    if(y[i] == Index(IINF,IINF,IINF))continue;
    int from = y[i].from;
    int to = y[i].to;
    if(used[to])continue;
    if(gused[group[to]])continue;
    int e = y[i].edge;
    used[to] = true;
    gused[group[to]] = true;
    prev.push_back(y[i]);
    tree[from].push_back(edge(to,e));
  }
  delete [] ngroup;
  delete [] y;
  delete [] sub;
}

struct Data{
  int u,v,b,c;
  Data(int u=IINF,int v=IINF,int b=IINF,int c=IINF):u(u),v(v),b(b),c(c){}
};

void cdfs(const vve &G,int cur,bool *visited){
  if(visited[cur])return;
  visited[cur] = true;
  rep(i,G[cur].size()) cdfs(G,G[cur][i].to,visited);
}


bool check(const vve &G,int root){
  bool visited[G.size()];
  rep(i,G.size())visited[i] = false;
  cdfs(G,root,&visited[0]);
  rep(i,G.size())if(!visited[i])return false;
  return true;
}

int main(){
  int C,T,CNT = 1;
  cin >> T;
  while(T--){
    Error = false;
    int root = 0;
    scanf("%d %d %d",&N,&M,&C);

    vve G(N);
    vector<Data> input;
    rep(i,M){
      int u,v,b,c;
      scanf("%d %d %d %d",&u,&v,&b,&c);
      input.push_back(Data(u,v,b,c));
    }

    long long ans = -1;
    long long L = 0,R =IINF,M=0;
    rep(_,60){
      M = ( L + R ) / 2;
      rep(i,N)G[i].clear();
      rep(i,input.size()){
	if( (long long)input[i].b >= M ){
	  G[input[i].u].push_back(edge(input[i].v,input[i].c));
	}
      }

      vve tree(N); //最終的なツリー
      bool used[N];//既にエッジをはられたか
      int group[N];  //どのグループに属しているのか
      bool group_used[N];
      vector<Index> pre; // 前にどのノードを使ったか
      rep(i,N)used[i] = group_used[i] = false,group[i] = i;
      Error = false;

      if(!check(G,root))Error = true;


      if(!Error) Minimum_Cost_Arborescence_Algorithm(N,root,G,tree,&used[0],&group[0],&group_used[0],pre);

      long long cost = 0;
      rep(i,N){
	rep(j,tree[i].size()){
	  cost += G[i][tree[i][j].cost].cost;
	}
      }

      if( cost > (long long) C || Error){
	R = M;
      } else {
	L = M;
	ans = max(ans,L);
      }
    }
    if( ans == -1 )cout << "streaming not possible." << endl;
    else           cout << ans << " kbps" << endl;
  }
    
  return 0;
}