[BZOJ 2118]墨墨的等式

论如何把数论乱搞和图论乱搞出在一起……

这个题由于要求[tex]x\ge 0[/tex],所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex](忽略为0的情况,为啥取最小值待会再说),对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex],将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex],同余方程都成立。

取模后,[tex]B\in Z_p[/tex],所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解(所以说,剩余系越少效率越高,这也就要求取的[tex]a_i[/tex]要小)。不过这个最小的一组合法解怎么找?

我们先找出任意一个合法[tex]B[/tex](比如说0吧),然后尝试加上[tex]a_i[/tex],就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。

求出来的最短路,表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数(能加多少[tex]p[/tex],就有多少个,注意不要忽略加0个的情况),并且答案符合区间减法,最后做差分即可。

注意忽略[tex]a_i=0[/tex]的情况(相当于不存在)。

代码:

/**************************************************************
    Problem: 2118
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1952 ms
    Memory:5508 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
    register int i,u,to;
    queue<int> Q;
    memset(d,0x7f,sizeof(d));
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    #ifdef DEBUG
    assert(d[1]==INF);
    #endif
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        for(i=1;i<=n;i++){
            to=(u+A[i])%minv;
            if(d[u]<INF && d[u]+A[i]<d[to]){
                d[to]=d[u]+A[i];
                if(!inQueue[to]){
                    Q.push(to);
                    inQueue[to]=true;
                }
            }
        }
    }
}
 
inline ll Calc(ll x){
    register ll ans=0;
    register int i=0;
    for(i=0;i<minv;i++)
        if(d[i]<=x)
            ans+=(x-d[i])/minv+1;
    return ans;
}
 
int main(){
    ll l,r;
    register int i;
    scanf("%d%lld%lld",&n,&l,&r);
    minv=0x7fffffff;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        if(!A[i]){
            i--;
            n--;
            continue;
        }
        minv=min(minv,A[i]);
    }
    SPFA();
    printf("%lld\n",Calc(r)-Calc(l-1));
    return 0;
}


[CodeVS 1098]均分纸牌

很妙的一个贪心啊……

根据题意,易求平均值。然后每个数减去平均值表示这个数和平均数的“差异”。然后呢?如果每个数的差异值不为0,就直接摊给下一堆。

这种做法最大的精髓在于,即使差异值为负,也能摊给下一堆,从而避免了各种复杂操作。

代码:

#include <iostream>
using namespace std;
const int maxn=105;
int A[maxn];
int main(){
	register int i,sum=0,ans=0;
	int n;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	sum/=n;
	for(i=1;i<=n;i++){
		A[i]-=sum;
	}
	for(i=1;i<=n;i++){
		if(A[i]!=0){
			ans++;
			A[i+1]+=A[i];
			A[i]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

[UOJ 19]寻找道路

这个题难就难在,别说重边自环,就是简单有向环,也会让DFS爆炸。所以考虑BFS。

但……BFS怎么判断其他点到[tex]t[/tex]的联通?

方法是,把边都反过来!这样BFS一遍就可以判联通了。

然后接下来BFS最短路就简单了,注意一些特判。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=10005,maxm=400005;
#define REP(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[maxm],to[maxm];
bool rev[maxm];
int graph_tot=0;
inline void AddEdge(int u,int v,bool reverse=false){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
    rev[graph_tot]=reverse;
}

int s,t;
bool vis[maxn];
bool LT[maxn];
bool bfs_1(){
    register int i,u;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(t);
    vis[t]=true;
    LT[t]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        GRAPH_REP(i,u){
            if(rev[i] && !vis[to[i]]){
                LT[to[i]]=true;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return LT[s];
}

int dep[maxn];
int bfs_2(){
    register int i,u;
    bool Allow;
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s]=true;
    dep[s]=0;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        Allow=true;
        GRAPH_REP(i,u){
            if(!rev[i] && !LT[to[i]]){
                Allow=false;
                break;
            }
        }
        if(!Allow)
            continue;
        GRAPH_REP(i,u){
            if(!rev[i] && !vis[to[i]]){
                dep[to[i]]=dep[u]+1;
                Q.push(to[i]);
                vis[to[i]]=true;
            }
        }
    }
    return vis[t]?dep[t]:-1;
}

int main(){
    int n,m,u,v;
    register int i;
    scanf("%d%d",&n,&m);
    REP(i,m){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u,true);
    }
    scanf("%d%d",&s,&t);
    if(!bfs_1()){
        puts("-1");
    }else{
        printf("%d\n",bfs_2());
    }
    return 0;
}

[UOJ 16]联合权值

这个题的关键啊……就在于那个中间点。

我们可以枚举中间点,然后进行统计。

至于最大联合权值,直接找中间点相邻点中最大权值和次大权值的积的最大值。至于联合权值之和,可以推出这样一个式子([tex]x[/tex]与中间点相邻,其中[tex]s[/tex]是所有和中间点相邻的点的权值和):

[tex]\Sigma x\mul (s-x)[/tex]

这就好弄多了。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=2*1e5+5;
const int maxm=maxn*2,MOD=10007;
#define REP(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[maxm],to[maxm];
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 pow_mod(int a,int b){
//     if(!b){
//         return 1;
//     }
//     int x=pow_mod(a,b>>1);
//     long long ans=(((long long)x)*((long long)x))%MOD;
//     if(1&b)
//         ans=ans*(a%MOD)%MOD;
//     return (int)ans;
// }
int d[maxn];
int main(){
    int n,u,v,temp,temp2;
    register int i,j,ans1=0,ans2=0,sum,maxv,smax;
    scanf("%d",&n);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    REP(i,n){
        scanf("%d",&d[i]);
    }
    REP(i,n){
        sum=maxv=smax=0;
        GRAPH_REP(j,i){
            temp=to[j];
            sum=(d[temp]%MOD+sum)%MOD;
            if(d[temp]>maxv){
                smax=maxv;
                maxv=d[temp];
            }else{
                if(d[temp]>smax)
                    smax=d[temp];
            }
        }
        ans1=max(ans1,maxv*smax);
        temp2=0;
        GRAPH_REP(j,i){
            temp=to[j];
            temp2=(temp2+(d[temp]%MOD)*((sum-(d[temp]%MOD)+MOD)%MOD)%MOD)%MOD;
        }
        ans2=(ans2+temp2)%MOD;
    }
    printf("%d %d\n",ans1,ans2);
    return 0;
}

[BZOJ 1217]消防局的设立

很明显可以看出消防局距离为5的话最划算……然后贪心就行了,顺便注意下根节点处理

代码:

/**************************************************************
    Problem: 1217
    User: danihao123
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:844 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
#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_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int ans=0;
int d[maxn];
void dfs(int x,int fa=-1){
    int maxq=-maxn,minq=maxn;
    int i;
    GRAPH_REP(i,x)
        if(to[i]!=fa){
            dfs(to[i],x);
            maxq=max(maxq,d[to[i]]);
            minq=min(minq,d[to[i]]);
        }
    if(minq+maxq<=3)
        d[x]=minq+1;
    else
        d[x]=maxq+1;
    if(minq==maxn)
        d[x]=3;
    if(d[x]==5){
        ans++;
        d[x]=0;
    }else{
        if(fa==-1 && d[x]>2)
            ans++;
    }
}
 
int main(){
    int n,v;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=(n-1);i++){
        scanf("%d",&v);
        AddEdge(i+1,v);
        AddEdge(v,i+1);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

[COGS 727]太空飞行计划

第一次做最大权闭合图……so sad

关于最大权闭合图的做法,可以参考胡伯涛前辈的《最小割模型在信息学竞赛中的应用》。不过很麻烦的事是……打印方案。

注意,割走的边要么和[tex]S[/tex]相连,要么就和[tex]T[/tex]相连。如果一条从[tex]S[/tex]到[tex]E_i[/tex]被割走了,那么就说明[tex]E_i[/tex]没有被选择;如果一条从[tex]I_i[/tex]到[tex]T[/tex]的边被割走了,那么就说明[tex]I_i[/tex]被选择了。

于是乎,Dinic最后一次造层次图的时候(这次最终将不能到达[tex]T[/tex]),如果某个点(除了[tex]S[/tex]和[tex]T[/tex])被访问到了,那个点就被选择了。

最小割的结果是所有拒绝的实验的能赚的钱及所有选用的仪器消耗的钱的和。也就是说,答案就是[tex]p[/tex]的和减去最小割。

代码:

#include <cstdio>
#include <iostream>
#include <iterator>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=211;
const int INF=0x7fffffff;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
  
struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    vector<Edge> edges;
    vector<int> G[maxn];
    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 d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Mincut(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,INF);
        }
        return ans;
    }
};

vector<int> AnsList;
int main(){
    register int i,j,ans=0;
    int m,n,p,x;
    bool flag;
    string line;
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    freopen("shuttle.in","r",stdin);
    freopen("shuttle.out","w+",stdout);
    ostream_iterator<int> output(cout," ");
    scanf("%d %d\n",&m,&n);
    REP_B(i,m){
        getline(cin,line);
        stringstream ss(line);
        ss>>p;
        ans+=p;
        Dinic::AddEdge(0,i,p);
        while(ss>>x){
            Dinic::AddEdge(i,m+x,INF);
        }
    }
    REP_B(i,n){
        cin>>p;
        Dinic::AddEdge(i+m,n+m+1,p);
    }
    ans-=Dinic::Mincut(0,n+m+1);
    REP_B(i,m){
        if(Dinic::vis[i]){
            AnsList.push_back(i);
        }
    }
    copy(AnsList.begin(),AnsList.end(),output);
    cout<<endl;
    AnsList.clear();
    REP_B(i,n){
        if(Dinic::vis[i+m]){
            AnsList.push_back(i);
        }
    }
    copy(AnsList.begin(),AnsList.end(),output);
    cout<<endl;
    cout<<ans<<endl;
    return 0;
}

[POJ 2455]Secret Milking Machine

这个题要求最大边最小,很明显要二分答案。

考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图,然后判断是否有[tex]T[/tex]条从1到N的不重复路径。

不过这个怎么做呢?我们可以把边加入(注意我们要加入的边都是无向边),并把容量设为1,从1到N跑一遍最大流,就是不重复路径条数。

为什么可以这样呢?每个边容量只有1,最多只能让一条路径使用并“推送”到终点,所以从1到N的最大流就是不重复路径条数辣。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

namespace Dinic{
	struct Edge{
		int u,v,cap,flow;
	};
    vector<Edge> edges;
    vector<int> G[maxn];
    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);
    }
	inline void ClearGraph(){
		register int i;
		edges.clear();
		m=0;
		REP(i,maxn){
			G[i].clear();
		}
	}
    bool vis[maxn];
    int d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
	register int i;
	Dinic::ClearGraph();
	REP_B(i,p){
		if(EdgePool[i].d>x)
			break;
		Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
		Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
	}
	if((Dinic::Maxflow(1,n))<t)
		return false;
	else
		return true;
}
int main(){
	register int i,L=0,M,R=0;
	scanf("%d%d%d",&n,&p,&t);
	REP_B(i,p){
		scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
		R=max(R,EdgePool[i].d+1);
	}
	sort(EdgePool+1,EdgePool+1+p);
	while(L<R){
		M=L+(R-L)/2;
		if(Check(M))
			R=M;
		else
			L=M+1;
	}
	printf("%d\n",L);
	return 0;
}

[COGS 732]试题库

这个题和那个圆桌聚餐很像。

不过注意一点,一个题如果有多种类型,那么那个题最后只能归结到一种题型中。有些同学可能就因此怀疑样例(尽管有SPJ)。

所以最后的建图就是这样:从[tex]S[/tex]向所有题目结点连一条容量为1的边,每个题目向对应题型连一条容量为1的边,每个题型向[tex]T[/tex]连一条容量为该类型题目需要数量的边。跑一遍最大流即可,当且仅当最大流为[tex]m[/tex]时有解。

输出解吧其实也不难,直接判断从题目结点出发的弧是否满载即可。注意不要把反向弧和普通弧弄混。

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1030,maxk=25;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
struct Edge{
    int u,v,cap,flow;
};
namespace Dinic{
    vector<Edge> edges;
    vector<int> G[maxn];
    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 d[maxn],cur[maxn];
    int s,t;
    inline bool BFS(){
        register int i,u;
        queue<int> Q;
        CL_ARR(vis,0);
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            REP(i,G[u].size()){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    vis[e.v]=1;
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,temp;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                temp=DFS(e.v,min(a,e.cap-e.flow));
                if(temp>0){
                    e.flow+=temp;
                    edges[G[x][i]^1].flow-=temp;
                    flow+=temp;
                    a-=temp;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        s=S;
        t=T;
        register int ans=0;
        while(BFS()){
            CL_ARR(cur,0);
            ans+=DFS(s,0x7f7f7f7f);
        }
        return ans;
    }
};

vector<int> ans[maxn];
int main(){
	int k,n,u,p;
	register int i,j,m=0,flow;
	freopen("testlib.in","r",stdin);
	freopen("testlib.out","w+",stdout);
	scanf("%d%d",&k,&n);
	REP_B(i,k){
		scanf("%d",&u);
		m+=u;
		Dinic::AddEdge(i+n,k+n+1,u);
	}
	REP_B(i,n){
		scanf("%d",&p);
		Dinic::AddEdge(0,i,1);
		REP_B(j,p){
			scanf("%d",&u);
			Dinic::AddEdge(i,n+u,1);
		}
	}
	flow=Dinic::Maxflow(0,n+k+1);
	if(flow!=m){
		puts("NoSolution!");
		return 0;
	}
	REP_B(i,n){
		for(j=0;j<Dinic::G[i].size();j++){
			Edge& e=Dinic::edges[Dinic::G[i][j]];
			if(e.v>n && e.v<=(n+k) && e.cap==e.flow){
				ans[e.v-n].push_back(i);
			}
		}
	}
	REP_B(i,k){
		printf("%d:",i);
		REP(j,ans[i].size()){
			printf(" %d",ans[i][j]);
		}
		putchar('\n');
	}
	return 0;
}

 

[BZOJ 1711]吃饭

这道题当初竟然没A……so sad

这题的建图要这么来:吃的、喝的、牛什么的统统拉进图里(不过牛本身只能同时享受一种食物,所以说点容量为1,要拆成俩点)。对于吃的,从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可(注意要拆成俩点!)。

代码:

/**************************************************************
    Problem: 1711
    User: danihao123
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=405,INF=0x7f7f7f7f;
 
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    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 d[maxn];
    int s,t;
    bool BFS(){
        register int i,x;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        d[s]=0;
        Q.push(s);
        vis[s]=true;
        while(!Q.empty()){
            x=Q.front();
            Q.pop();
            for(i=0;i<G[x].size();i++){
                Edge& e=edges[G[x][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[x]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int cur[maxn];
    int DFS(int x,int a){
        if(x==t || a==0)
            return a;
        int flow=0,f;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(d[e.v]==d[x]+1){
                f=DFS(e.v,min(a,e.cap-e.flow));
                if(f>0){
                    flow+=f;
                    e.flow+=f;
                    edges[G[x][i]^1].flow-=f;
                    a-=f;
                    if(a==0)
                        break;
                }
            }
        }
        return flow;
    }
    inline int Maxflow(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            ans+=DFS(s,INF);
        }
        return ans;
    }
};
int main(){
    int N,F,D,f,d,x;
    register int i,j,t;
    scanf("%d%d%d",&N,&F,&D);
    t=2*N+F+D+1;
    for(i=1;i<=F;i++)
        Dinic::AddEdge(0,i,1);
    for(i=2*N+F+1;i<t;i++)
        Dinic::AddEdge(i,t,1);
    for(i=1;i<=N;i++)
        Dinic::AddEdge(F+2*i-1,F+2*i,1);
    for(i=1;i<=N;i++){
        scanf("%d%d",&f,&d);
        for(j=1;j<=f;j++){
            scanf("%d",&x);
            Dinic::AddEdge(x,2*i-1+F,1);
        }
        for(j=1;j<=d;j++){
            scanf("%d",&x);
            Dinic::AddEdge(2*i+F,F+2*N+x,1);
        }
    }
    printf("%d\n",Dinic::Maxflow(0,t));
    return 0;
}

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