[CF 711D]Directed Roads
这个题啊……其实不难。
首先你注意,他告诉你你可以把边弄反。
其次注意,这个图不一定就有一个环。
然后每个环的取反法有[tex]2^x[/tex]种(假设环中有[tex]x[/tex]条边),但是空集不行,全集也不行,因此每个环爆掉的方案有[tex]2^x-2[/tex]种。然后环之外的边随便弄,乘法原理乱搞即可。
然后你是不是感觉这个题似曾相识?是的似乎这个题就是NOIP D1T2的翻版。
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int maxn=200001; const ll MOD=1000000007; int G[maxn]; int in[maxn]; bool vis[maxn]; int n; inline bool jianz(){ register int i; bool ans=false; for(i=1;i<=n;i++){ if(!vis[i] && !in[i]){ ans=true; in[G[i]]--; vis[i]=true; G[i]=0; } } return ans; } ll dfs(int x,int y){ if(x==y && vis[x]){ return 0; }else{ vis[x]=true; return dfs(G[x],y)+1; } } ll pow_mod(ll a,ll b){ if(!b){ return 1; }else{ ll ans=pow_mod(a,b/2); ans=ans*ans%MOD; if(1&b){ ans=(ans*(a%MOD))%MOD; } return ans; } } inline ll solve(){ register int i; register ll Huan,temp=0,ans=1; while(jianz()); for(i=1;i<=n;i++) if(!vis[i]){ Huan=dfs(i,i); temp+=Huan; ans=(ans*(pow_mod(2,Huan)+MOD-2))%MOD; } ans=(ans*pow_mod(2,n-temp))%MOD; return ans; } int main(){ register int i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&G[i]); in[G[i]]++; } printf("%I64d\n",solve()); return 0; }
[BZOJ 1715]虫洞
呜……这题现在才A
这道题就是给一个图让判断有没有负环,没什么难度
然后……我写邻接表竟然开小内存了……
尽管如此我感觉我写此题时的代码风格还是不错的,比较值得学习
代码:
/************************************************************** Problem: 1715 User: danihao123 Language: C++ Result: Accepted Time:92 ms Memory:920 kb ****************************************************************/ #include <cstdio> #include <queue> #include <cstring> #include <cctype> using namespace std; const int maxn=501,maxm=5201; namespace Graph{ int n; int first[maxn]; int next[maxm],to[maxm],dist[maxm]; int tot=0; inline void AddEdge(int u,int v,int d){ tot++; next[tot]=first[u]; first[u]=tot; to[tot]=v; dist[tot]=d; } inline void ClearGraph(){ memset(first,0,sizeof(first)); memset(next,0,sizeof(next)); memset(to,0,sizeof(to)); memset(dist,0,sizeof(dist)); tot=0; } int cnt[maxn]; bool inQueue[maxn]; int d[maxn]; bool SPFA(){ register int i,u; queue<int> Q; memset(cnt,0,sizeof(cnt)); memset(inQueue,0,sizeof(inQueue)); for(i=1;i<=n;i++){ d[i]=0; cnt[i]=1; inQueue[i]=true; Q.push(i); } while(!Q.empty()){ u=Q.front(); Q.pop(); inQueue[u]=false; for(i=first[u];i;i=next[i]){ if(d[to[i]]>d[u]+dist[i]){ d[to[i]]=d[u]+dist[i]; if(!inQueue[to[i]]){ Q.push(to[i]); inQueue[to[i]]=true; if(++cnt[to[i]]>n) return true; } } } } return false; } }; inline int readint(){ register char c; register int temp=0; c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ temp=temp*10+c-'0'; c=getchar(); } return temp; } int main(){ register int i,m,w,u,v,d; int F; F=readint(); while(F--){ Graph::n=readint(); m=readint(); w=readint(); Graph::ClearGraph(); for(i=1;i<=m;i++){ u=readint(); v=readint(); d=readint(); Graph::AddEdge(u,v,d); Graph::AddEdge(v,u,d); } for(i=1;i<=w;i++){ u=readint(); v=readint(); d=readint(); Graph::AddEdge(u,v,-d); } if(Graph::SPFA()) puts("YES"); else puts("NO"); } return 0; }
[BZOJ 1002]轮状病毒
根据Matrix-Tree定理,这题可以求出基尔霍夫矩阵,然后当成行列式求值即可
这样做并没有什么错,大概也能AC,但是时间复杂度是立方级的,并且写起来并不简单(要用到高斯消元什么的,更何况此题还要用高精度)
或许DP也可以?
不过有一个简单的递推式:d[n]=d[n-1]*3-d[n-2]+2
证明比较麻烦(绝大多数人是找规律出来的),可以到这找:http://vfleaking.blog.163.com/blog/static/17480763420119685112649
这题要用高精也太烦人了,我就用了Python写(Python语法真特么烦人啊)
Q:真要考试你交Python啊?
A:我用Python打出来表然后交表啊。
代码: