[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;
}

[洛谷 P2661]信息传递

bi了doge了……图论基本不会了……

这提可以直接循环删除所有入度为0的边,这样就只剩环了。然后DFS嘿嘿嘿。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200001;
int G[maxn];
int to[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !to[i]){
            ans=true;
            to[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
int dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
int getchen(){
    register int i,ans=0x5ffffff;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i])
            ans=min(ans,dfs(i,i));
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        to[G[i]]++;
    }
    printf("%d\n",getchen());
    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打出来表然后交表啊。

代码:

继续阅读