[BZOJ 2190]仪仗队

这个题啊……有规律可循。

我们可以发现,关于答案[tex]a[/tex]有如下规律:

[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]

然后筛法求欧拉函数即可(我听说神犇们都用了杜教筛哎)

代码:

/**************************************************************
    Problem: 2190
    User: danihao123
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:976 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int phi[maxn];
int n;
void sieve(){
    register int i,j;
    phi[1]=1;
    CUS_REP(i,2,n)
        if(!phi[i])
            for(j=i;j<=n;j+=i){
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}
 
int main(){
    register int i,ans=2;
    scanf("%d",&n);
    sieve();
    /*
    #ifdef DEBUG
    CUS_REP(i,1,n)
        printf("%d\n",phi[i]);
    #endif
    */
    CUS_REP(i,2,n-1)
        ans+=phi[i];
    printf("%d\n",ans*2-1);
    return 0;
}


[BZOJ 1520]Szk-Schools

这个是二分图最小权完美匹配啦……不过我还是写的费用流。

不过注意一定要判断是否有完美匹配。

代码:

/**************************************************************
    Problem: 1520
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2016 ms
    Memory:5004 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=410;
namespace MCMF{
    struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    inline void ClearGraph(){
        register int i;
        edges.clear();
        for(i=0;i<maxn;i++)
            G[i].clear();
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,int& flow,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        flow+=a[t];
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t,int& flow){
        register long long ans=0;
        while(BellmanFord(s,t,flow,ans));
        return ans;
    }
};
int main(){
    int n,m,a,b,k;
    register int i,j,cost,flow=0;
    register long long ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&m,&a,&b,&k);
        for(j=a;j<=b;j++){
            cost=k*abs(j-m);
            MCMF::AddEdge(i,j+n,1,cost);
        }
    }
    for(i=1;i<=n;i++)
        MCMF::AddEdge(0,i,1,0);
    for(i=n+1;i<=2*n;i++)
        MCMF::AddEdge(i,2*n+1,1,0);
    ans=MCMF::MincostMaxflow(0,2*n+1,flow);
    if(flow<n)
        puts("NIE");
    else
        printf("%lld\n",ans);
    return 0;
}

[COGS 740]分配问题

很明显是二分图最大权匹配。可以用匈牙利算法求解,但我比较弱……所以就写了个费用流。

注意最优解和最差解都要给出!

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205;
namespace MCMF{
	struct Edge{
		int u,v,cap,flow,cost;
	};
	vector<Edge> edges;
	vector<int> G[maxn];
	int m;
	inline void AddEdge(int u,int v,int cap,int cost){
		edges.push_back((Edge){u,v,cap,0,cost});
		edges.push_back((Edge){v,u,0,0,-cost});
		m=edges.size();
		G[u].push_back(m-2);
		G[v].push_back(m-1);
	}
	inline void ClearGraph(){
		register int i;
		edges.clear();
		for(i=0;i<maxn;i++)
			G[i].clear();
	}
	int a[maxn];
	bool inQueue[maxn];
	int d[maxn],p[maxn];
	bool BellmanFord(int s,int t,long long& cost){
		register int i,u;
		queue<int> Q;
		memset(d,0x7f,sizeof(d));
		memset(inQueue,0,sizeof(inQueue));
		d[s]=0;
		inQueue[s]=true;
		p[s]=0;
		a[s]=0x7f7f7f7f;
		Q.push(s);
		while(!Q.empty()){
			u=Q.front();
			Q.pop();
			inQueue[u]=false;
			for(i=0;i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
					d[e.v]=d[u]+e.cost;
					p[e.v]=G[u][i];
					a[e.v]=min(a[u],e.cap-e.flow);
					if(!inQueue[e.v]){
						Q.push(e.v);
						inQueue[e.v]=true;
					}
				}
			}
		}
		if(d[t]==0x7f7f7f7f)
			return false;
		cost+=((long long)d[t])*((long long)a[t]);
		for(u=t;u!=s;u=edges[p[u]].u){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
		}
		return true;
	}
	long long MincostMaxflow(int s,int t){
		register long long ans=0;
		while(BellmanFord(s,t,ans));
		return ans;
	}
};
int A[105][105];
int main(){
	int n;
	register int i,j;
	freopen("job.in","r",stdin);
	freopen("job.out","w+",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			scanf("%d",&A[i][j]);
			MCMF::AddEdge(i,j+n,1,A[i][j]);
		}
	for(i=1;i<=n;i++)
		MCMF::AddEdge(0,i,1,0);
	for(i=n+1;i<=2*n;i++)
		MCMF::AddEdge(i,2*n+1,1,0);
	printf("%lld\n",MCMF::MincostMaxflow(0,2*n+1));
	MCMF::ClearGraph();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			MCMF::AddEdge(i,j+n,1,-A[i][j]);
		}
	for(i=1;i<=n;i++)
		MCMF::AddEdge(0,i,1,0);
	for(i=n+1;i<=2*n;i++)
		MCMF::AddEdge(i,2*n+1,1,0);
	printf("%lld\n",-(MCMF::MincostMaxflow(0,2*n+1)));
	return 0;
}

[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查

这个是一道题啊……不过都是挺经典的问题……

建图是这样的:支持0的从[tex]S[/tex]向此点连一条容量为1的边,支持1的就向[tex]T[/tex]连一条长度为1的边,朋友之间连一条长度为1的边。跑一遍最小割即可。

这个的解释?最优情况下任何人违背自己的意见都是因为怕和朋友冲突,和朋友冲突则是因为没有违背自己的意见(废话)。所以拆了最小割就解决掉了所有冲突问题。

代码:

/**************************************************************
    Problem: 2768
    User: danihao123
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:7668 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int s,t;
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int cur[maxn],d[maxn];
    bool bfs(){
        register int i,u;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t || a==0)
            return a;
        int f,flow=0;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
                flow+=f;
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }
    int MinCut(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            ans+=dfs(s,0x7fffffff);
        }
        return ans;
    }
};
int main(){
    int n,m;
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&u);
        if(!u){
            Dinic::AddEdge(0,i,1);
        }else{
            Dinic::AddEdge(i,n+1,1);
        }
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        Dinic::AddEdge(u,v,1);
        Dinic::AddEdge(v,u,1);
    }
    printf("%d\n",Dinic::MinCut(0,n+1));
    return 0;
}

[BZOJ 3531]旅行

发现自己好久没写树链剖分了……唉……

言归正传,这道题很容易想到的做法就是每种宗教开一个线段树,到各个宗教的线段树里面操作即可。

很可惜,直接开线段树的话肯定会MLE。我们可以考虑动态开点,对于不需要的点一律不开。这样内存消耗量就大减了。

注意一些细节:

  1. 查询时判断当前结点是不是NULL。
  2. 删除前最好判断一下这个结点是不是NULL吧,以防万一。
  3. 删除操作时,如果结点没有用了,就删。但是注意,记得delete前要把原指针设为NULL,直接delete会引起悬垂指针问题导致爆炸!

代码:

/**************************************************************
    Problem: 3531
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10404 ms
    Memory:34872 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
    struct Node{
        int sumv,maxv;
        Node *lc,*rc;
        Node(){
            sumv=maxv=0;
            lc=rc=NULL;
        }
        void maintain(){
            if(lc!=NULL){
                if(rc!=NULL){
                    sumv=lc->sumv+rc->sumv;
                    maxv=max(lc->maxv,rc->maxv);
                }else{
                    sumv=lc->sumv;
                    maxv=lc->maxv;
                }
            }else{
                if(rc!=NULL){
                    sumv=rc->sumv;
                    maxv=rc->maxv;
                }
            }
        }
    };
    Node* T[maxn];
    int p,v;
    void _Delete(Node* &o,int L,int R){
        if(o==NULL)
            return;
        if(L==R){
            Node *temp=o;
            o=NULL;
            delete temp;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Delete(o->lc,L,M);
            else
                _Delete(o->rc,M+1,R);
            if(o->lc==NULL && o->rc==NULL){
                Node *temp=o;
                o=NULL;
                delete temp;
            }else{
                o->maintain();
            }
        }
    }
    inline void Delete(int c,int pos){
        p=pos;
        _Delete(T[c],1,n);
    }
    void _Insert(Node* &o,int L,int R){
        if(o==NULL)
            o=new Node();
        if(L==R){
            o->sumv=o->maxv=v;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Insert(o->lc,L,M);
            else
                _Insert(o->rc,M+1,R);
        }
        o->maintain();
    }
    inline void Insert(int c,int pos,int value){
        p=pos;
        v=value;
        _Insert(T[c],1,n);
    }
    int ql,qr;
    int _query_max(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->maxv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans=max(ans,_query_max(o->lc,L,M));
        if(qr>M)
            ans=max(ans,_query_max(o->rc,M+1,R));
        return ans;
    }
    inline int query_max(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_max(T[c],1,n);
    }
    int _query_sum(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->sumv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans+=_query_sum(o->lc,L,M);
        if(qr>M)
            ans+=_query_sum(o->rc,M+1,R);
        return ans;
    }
    inline int query_sum(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_sum(T[c],1,n);
    }
};
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}
 
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hld_cnt;
    SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
int query_max(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_max(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_sum(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
    int c=rlg[pos];
    SegmentTree::Delete(c,tid[pos]);
    SegmentTree::Insert(direction,tid[pos],d[pos]);
    rlg[pos]=direction;
}
inline void Update(int pos,int v){
    d[pos]=v;
    SegmentTree::Insert(rlg[pos],tid[pos],v);
}
 
int main(){
    register int i;
    int q,u,v;
    char buf[5];
    scanf("%d%d",&n,&q);
    REP_B(i,n){
        scanf("%d%d",&d[i],&rlg[i]);
    }
    REP_B(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    while(q--){
        memset(buf,0,sizeof(buf));
        scanf("%s%d%d",buf,&u,&v);
        if(buf[0]=='C'){
            if(buf[1]=='W'){
                Update(u,v);
            }else{
                Replace(u,v);
            }
        }else{
            if(buf[1]=='M'){
                printf("%d\n",query_max(rlg[u],u,v));
            }else{
                printf("%d\n",query_sum(rlg[u],u,v));
            }
        }
    }
    return 0;
}

[BZOJ 2054]疯狂的馒头

秒,秒啊……

很容易想到线段树,但是在[tex]N=10^6,M=10^7[/tex]的情况下,线段树肯定会TLE。

考虑修改,我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作,然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集!每个节点修改完后将其父亲改为下一个点,这样的话被修改的地方就可以轻松跳过了。

注意一个细节,第[tex]N[/tex]个馒头被染色后,其父亲会被修改为[tex]N+1[/tex],所以说并查集实际上要开[tex]N+1[/tex]!

代码:

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}

[洛谷 P1962]斐波那契数列

线性代数的很多知识用一句欠揍的话形容就是:只可意会,不可言传。

友矩阵就是一个。友矩阵是一种应用于求递归数列的一种矩阵,作用是将一个旧的递归数列向量变成一个新的递归数列向量。友矩阵长相比较美(qi)观(pa),可以自行问度娘。

关于递归数列[tex]F[/tex],如果假设要用到的从前的信息可以组织为一个列向量[tex]F_{n-1}[/tex],若已知其友矩阵为[tex]A[/tex],则有下公式(这个推导其实并不难,如果你用解线性方程组的思维来看的话):

[tex]F_n=A\mul F_{n-1}[/tex]

可知(假设要用到的从前的信息为[tex]d[/tex]):

[tex]F_n=A^{n-d}*F_d[/tex]

然后我们发现求[tex]A^{n-d}[/tex]可以使用快速幂,这就简单了^_^

不过有个不错的小技巧:快速幂结果矩阵的初始值处理让人很头疼,不过可以直接使用单位矩阵,这样就相当于通常计算中的1辣~

代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[2][2];
const ull MOD=1000000007;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))

inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    Matrix C;
    register int i,j,k;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,ull x,Matrix& res){
    Matrix a,temp;
    register int i;
    bool used=false;
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    temp[0][0]=1;
    temp[1][1]=1;
    while(x){
        if(1&x){
            MatrixMul(temp,a,2,2,2,temp);
        }
        x>>=1;
        MatrixMul(a,a,2,2,2,a);
    }
    CP_ARR(temp,res);
}
Matrix Q={{0,1},{1,1}};
Matrix Fib={{1,0},{1,0}};
int main(){
    ull n;
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cin>>n;
    if(n<=2){
        cout<<1<<endl;
    }else{
        MatrixPow(Q,n-2,Q);
        MatrixMul(Q,Fib,2,2,1,Fib);
        cout<<Fib[1][0]<<endl;
    }
    return 0;
}

[POJ 1679]The Unique MST

又是一个上百行代码的题……

这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树,来判断MST的唯一性。

非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是,求出MST中待加入边两端路径上最大边,删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样,就说明MST不唯一。

代码:

#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
const int maxn=105,maxm=10005;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int first[maxn];
int next[205],to[205],dist[205];
int graph_cnt=0;
inline void AddEdge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
inline void ClearGraph(){
    CL_ARR(first,0);
    CL_ARR(next,0);
    CL_ARR(to,0);
    CL_ARR(dist,0);
    graph_cnt=0;
}

int anc[maxn][32],maxcost[maxn][32];
int dep[maxn];
void dfs(int x,int depth,int fa,int d){
    int i;
    dep[x]=depth;
    anc[x][0]=fa;
    maxcost[x][0]=d;
    GRAPH_REP(i,x){
        if(to[i]!=fa){
            dfs(to[i],depth+1,x,dist[i]);
        }
    }
}

int n;
inline void process(){
    register int i,j,a;
    dfs(1,0,0,0);
    for(j=1;(1<<j)<n;j++){
        REP(i,n){
            if(anc[i][j-1]!=-1){
                a=anc[i][j-1];
                anc[i][j]=anc[a][j-1];
                maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
            }
        }
    }
}

int query(int x,int y){
    register int tmp,log,i,ans=-0x7fffffff;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;(1<<log)<=dep[x];log++);
    log--;
    for(i=log;i>=0;i--)
        if(dep[x]-(1<<log)>=dep[y]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
        }
    if(x==y)
        return ans;
    for(i=log;i>=0;i--)
        if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){
            ans=max(ans,maxcost[x][i]);
            x=anc[x][i];
            ans=max(ans,maxcost[y][i]);
            y=anc[y][i];
        }
    ans=max(ans,maxcost[x][0]);
    ans=max(ans,maxcost[y][0]);
    return ans;
}

int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    REP(i,n)
        p[i]=i;
    CL_ARR(rank,0);
}

struct Edge{
    int u,v,d;
    bool operator <(const Edge& x) const{
        return d<x.d;
    }
};
#define ALL_FT(x) E[x].u,E[x].v
Edge E[maxm];
int m;
bitset<maxn> Choose;
int MST(){
    register int i,ans=0,cnt=0;
    ClearGraph();
    init_set();
    Choose.reset();
    sort(E+1,E+1+m);
    REP(i,m){
        if(!is_same(ALL_FT(i))){
            Choose[i]=true;
            cnt++;
            ans+=E[i].d;
            union_set(ALL_FT(i));
            AddEdge(ALL_FT(i),E[i].d);
            AddEdge(E[i].v,E[i].u,E[i].d);
        }
        if(cnt==(n-1)){
            break;
        }
    }
    return ans;
}
int main(){
    int T;
    int u,v,d;
    register int i,ans,temp;
    bool OK;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        REP(i,m){
            scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
        }
        ans=MST();
        CL_ARR(anc,-1);
        process();
        OK=true;
        REP(i,m){
            if(!Choose[i]){
                temp=query(ALL_FT(i));
                if(temp==E[i].d){
                    OK=false;
                    puts("Not Unique!");
                    break;
                }
            }
        }
        if(OK)
            printf("%d\n",ans);
    }
    return 0;
}

[BZOJ 3436]小K的农场

差分约束系统的可行性问题啊……

按照要求连边然后SPFA判负环即可。

代码:

/**************************************************************
    Problem: 3436
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9224 ms
    Memory:1488 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
 
int n;
namespace Graph{
    int first[maxn];
    int next[maxm],to[maxm];
    ll dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,ll d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
 
    bool inQueue[maxn];
    ll d[maxn];
    int cnt[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        REP(i,n){
            inQueue[i]=true;
            Q.push(i);
        }
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            GRAPH_REP(i,u){
                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 false;
                    }
                }
            }
        }
        return true;
    }
};
 
int main(){
    int m,opt,a,b,c;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d%d",&opt,&a,&b);
        if(opt==1){
            scanf("%d",&c);
            Graph::AddEdge(a,b,-c);
        }else{
            if(opt==2){
                scanf("%d",&c);
                Graph::AddEdge(b,a,c);
            }else{
                Graph::AddEdge(a,b,0);
                Graph::AddEdge(b,a,0);
            }
        }
    }
    if(Graph::SPFA())
        puts("Yes");
    else
        puts("No");
    return 0;
}

[BZOJ 2330]糖果

比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT

这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。

顺便说一些这题的坑点:

  1. 有一个点是一个十万个点的链。在从源点连的时候,如果正序连就会炸。倒着连就不会T。
  2. 有的点的2,4条件出现了[tex]a=b[/tex]的情况,要特判……
  3. 要开long long!

代码:

/**************************************************************
    Problem: 2330
    User: danihao123
    Language: C++
    Result: Accepted
    Time:356 ms
    Memory:7592 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
 
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
    register int i,u;
    register ll ans=0;
    queue<int> Q;
    CL_ARR(d,-1);
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        GRAPH_REP(i,u){
            if(d[u]>-1 && 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+1))
                        return -1;
                }
            }
        }
    }
    REP(i,n){
        ans+=d[i];
    }
    return ans;
}
 
int main(){
    register int i;
    int opt,u,v;
    int k;
    scanf("%d%d",&n,&k);
    REP(i,k){
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1){
            AddEdge(u,v,0);
            AddEdge(v,u,0);
        }else{
            if(opt==2){
                if(u==v){
                    puts("-1");
                    return 0;
                }
                AddEdge(u,v,1);
            }else{
                if(opt==3){
                    AddEdge(v,u,0);
                }else{
                    if(opt==4){
                        if(u==v){
                            puts("-1");
                        }
                        AddEdge(v,u,1);
                    }else{
                        AddEdge(u,v,0);
                    }
                }
            }
        }
    }
    for(i=n;i>=1;i--){
        AddEdge(0,i,1);
    }
    printf("%lld\n",SPFA());
    return 0;
}