[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打出来表然后交表啊。
代码：
