ZOJ 2699 Police Cities(Codeforces Gym - 100211D) SCC+DP HQG_AC的博客

ZOJ 2699

Andrew Stankevich Contest 9(Codeforces)

题意：
有一个n个点，m条边的有向图，现在有布置k个点作为警察局，要求可以通过警察局从每个城市的道路到达某个城市，从警察局到某个城市的道路可以到达每个城市。

求出布置k个警察局可能数

首先看这个数据范围就要高精度 o(╥﹏╥)o

不爽 (•́へ•́╬)

先不提高精的事。

这题看着其实挺裸的。

一看又是 $SCC+DP$的模型 （SCC不会的请看裸题（Checkposts））

思考DP方程

$dp[i][j]$表示前个顶点安排j个警察局的方案数

对于没有入度或出度的点，我们单独考虑，因为这些点都必须放$Police$ $Station$

没有入度或出度用SCC解决

$dp[i][j] = \sum_{k = 0}^{k < j} dp[i-1][k]*c[x][j-k]$

代码细看，这个题是不错的。

对于高精度不熟悉的同学，建议用$Struct$定义$Biginteger$类，之后打一下模板

注意高精度请勿输出前导零

我也打了一天才AC

Code:

include 
using namespace std ;
const int N = 110;//高精模板开始 struct bign{int len,s[N];bign(){ memset(s,0,sizeof(s));len=1;}bign(int num){*this=num;}bign(char *num){*this=num;}bign operator =(int num){char c[N];sprintf(c,"%d",num);*this=c;return *this;}bign operator =(const char *num){len=strlen(num);for (int i=0;i1-i]-'0';return *this;}string str(){string res="";for (int i=0;ichar)(s[i]+'0')+res;return res;}void clean(){while (len>1&&!s[len-1]) len--;}bign operator +(const bign &b){bign c;    c.len=0;for (int i=0,g=0;g||iint x=g;if (iif (i10;g=x/10;}return c;}bign operator -(const bign &b){bign c;c.len=0;int x;     for (int i=0,g=0;iif (iif (x>=0) g=0;else{          x+=10;g=1;};c.s[c.len++]=x;}c.clean();return c;}bign operator *(const bign &b){bign c;c.len=len+b.len;for (int i=0;ifor (int j=0;jfor (int i=0;i1;i++) { c.s[i+1]+=c.s[i]/10; c.s[i]%=10; }c.clean();return c;  }bool operator <(const bign &b){if (len!=b.len) return lenfor (int i=len-1;i>=0;i--)if (s[i]!=b.s[i]) return s[i]return false;}bign operator +=(const bign &b){*this=*this+b;return *this;}bign operator -=(const bign &b){*this=*this-b;return *this;}  
};
istream& operator >>(istream &in,bign &x){string s;in>>s;x=s.c_str();return in;
}
ostream& operator <<(ostream &out,bign &x){out<return out;
}//高精大模板就此结束 vector <int> G[N],nod,hd ;//nod存储没有d的点 
stack <int> S ;
int link[N],din[N],dout[N],dfn[N],low[N],sd[N] ;
//link[i]表示SCC i有多少个点，din和dout分别表示i的入度和出度
//dfn和low是Trajan里要干的
//sd表示缩点
bool vis[N] ;
bign dp[N][N],c[N][N] ; 
int n,m,K,cnt,tot ;void tarjan(int now){ //tarjan ---> scc dfn[now]=low[now]=++tot ;vis[now]=true;S.push(now) ;for (int i=0;iint to=G[now][i] ;if (!dfn[to]){tarjan(to) ;low[now]=min(low[now],low[to]) ;}else if (vis[to]) low[now]=min(low[now],dfn[to]) ;}if (dfn[now]==low[now]){sd[now]=++cnt ;link[cnt]++ ;vis[now]=false ;while(S.top()!=now){sd[S.top()]=cnt; link[cnt]++ ;vis[S.top()]=false ;S.pop() ;} S.pop() ;}
}
void init_c(){ //预处理出C数组for(int i=0;i0]=c[i][i]=1 ;for (int j=1;j1][j-1]+c[i-1][j] ;}
}
void init(){tot=cnt=0 ;memset(dfn,0,sizeof(dfn)) ;memset(low,0,sizeof(low)) ;memset(vis,0,sizeof(vis)) ;memset(sd,0,sizeof(sd)) ; memset(link,0,sizeof(link)) ;memset(din,0,sizeof(din)) ;memset(dout,0,sizeof(dout)) ; memset(dp,0,sizeof(dp)) ;nod.clear() ;hd.clear() ;for (int i=0;i<=N;i++) G[i].clear() ;while (!S.empty()) S.pop() ;
}int main(){ios::sync_with_stdio(false) ;init_c() ; while(~scanf("%d%d%d",&n,&m,&K)){ init() ;for (int i=1;i<=m;i++){int x,y ; scanf("%d%d",&x,&y) ;G[x].push_back(y) ;}for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i) ;dp[0][0]=1 ;for (int i=1;i<=n;i++){for (int j=0;jint v=G[i][j] ;if (sd[i]==sd[v]) continue ;din[sd[v]]++;dout[sd[i]]++ ;}}for (int i=1;i<=cnt;i++)if (!din[i] || !dout[i]) nod.push_back(i) ;else hd.push_back(i) ;for (int i=1;i<=nod.size();i++)for (int j=1;j<=K;j++)for (int k=j-1;k>=0 && j-k<=link[nod[i-1]];k--)dp[i][j]+=dp[i-1][k]*c[link[nod[i-1]]][j-k] ;for (int i=nod.size()+1,t=0;i<=cnt;i++,t++)for (int j=nod.size();j<=K;j++)for (int k=nod.size();k<=j;k++)dp[i][j]+=dp[i-1][k]*c[link[hd[t]]][j-k] ;cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！