[UVa 10635]Prince and Princess

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到[tex][1,p+1][/tex],然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

[BZOJ 1511]Periods of Words

很妙的一道题啊。

这个题可以先求一遍KMP的失配函数,然后对于每个失配函数沿着失配边往前一直走(不能走到0)。然后对于每个前缀[tex]i[/tex],答案就是[tex]i-f[i][/tex](要求[tex]f[i][/tex]不为0,反之无解)。

为什么这样可以呢?

首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀,如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串,这个子串是不考虑的。当然,我们希望在这个被删除的子串最短辣。

代码:

/**************************************************************
    Problem: 1511
    User: danihao123
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:5704 kb
****************************************************************/
 
#include <cstdio>
const int maxn=1000005;
 
char buf[maxn];
int f[maxn];
int main(){
    register int i,j;
    register long long ans=0;
    int n;
    scanf("%d%s",&n,buf);
    f[0]=f[1]=0;
    for(i=1;i<n;i++){
        j=f[i];
        while(j && buf[i]!=buf[j])
            j=f[j];
        f[i+1]=(buf[i]==buf[j]?j+1:0);
    }
    for(i=2;i<=n;i++){
        if(f[i]){
            while(f[f[i]]){
                f[i]=f[f[i]];
            }
        }
    }
    for(i=1;i<=n;i++){
        if(f[i]){
            ans+=i-f[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

[BZOJ 1212]L语言

这个感觉本质上和那个Remember a Word很像吧……

不过这个只是求最长可行前缀,递推即可。

代码:

/**************************************************************
    Problem: 1212
    User: danihao123
    Language: C++
    Result: Accepted
    Time:660 ms
    Memory:45072 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
 
vector<int> AnsList;
namespace Trie{
    const int maxnode=400005;
    const int sigma_siz=26;
    int Tree[maxnode][sigma_siz];
    int val[maxnode];
    int siz;
    inline int idx(char c){
        return c-'a';
    }
    inline void InitTrie(){
        siz=0;
        val[0]=0;
        CL_ARR(Tree[0],0);
    }
    void Insert(char *s,int v){
        register int u=0,n=strlen(s);
        register int i,c;
        REP(i,n){
            c=idx(s[i]);
            if(!Tree[u][c]){
                siz++;
                Tree[u][c]=siz;
                val[siz]=0;
                CL_ARR(Tree[siz],0);
            }
            u=Tree[u][c];
        }
        val[u]=v;
    }
    void Query(char *s,int len){
        register int i,c,u=0;
        AnsList.clear();
        REP(i,len){
            if(!s[i])
                break;
            c=idx(s[i]);
            if(!Tree[u][c])
                break;
            u=Tree[u][c];
            if(val[u])
                AnsList.push_back(val[u]);
        }
    }
};
 
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
    int n,m;
    int length;
    register int i,j,k;
    bool flag;
    Trie::InitTrie();
    scanf("%d%d",&n,&m);
    REP_B(i,n){
        scanf("%s",buf);
        len[i]=strlen(buf);
        Trie::Insert(buf,i);
    }
    REP_B(i,m){
        scanf("%s",Text);
        length=strlen(Text);
        CL_ARR(d,0);
        d[0]=true;
        for(j=0;j<=length;j++){
            if(d[j]){
                Trie::Query(Text+j,length-j);
                REP(k,AnsList.size()){
                    d[j+len[AnsList[k]]]=true;
                }
            }
        }
        flag=false;
        for(j=length;j>=0;j--){
            if(d[j]){
                flag=true;
                printf("%d\n",j);
                break;
            }
        }
        if(!flag)
            puts("0");
    }
    return 0;
}

[POJ 2784]Buy or Build

啊这题竟然在POJ上有……

枚举套餐子集是肯定的啦,但接下来呢?有的同学或许会想直接Kruskal求MST。但是估计会T。

有一个很有效的优化:先求一遍不加套餐的MST,然后接下来每次求MST的时候都只考虑这[tex]n-1[/tex]条边,这样就很快了。

需要注意的是,这[tex]n-1[/tex]以外的边就算加入了套餐也不会被考虑。因为无论加不加套餐,这些更大的边所能连接的连通分量总是可以被以前更小的边连接,所以这条边无论如何也不会被考虑啦……

代码写起来容易让人崩溃……所以说这个题很能锻炼代码能力和Debug能力。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1005,maxq=8;
int n;

int p[maxn],rank[maxn];
int find_set(int x){
	if(p[x]==x)
		return x;
	else
		return p[x]=find_set(p[x]);
}
inline 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;
	for(i=1;i<=n;i++)
		p[i]=i;
	memset(rank,0,sizeof(rank));
}

int Cost[maxq];
vector<int> V[maxq];
struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
vector<Edge> bj;
vector<Edge> E;
vector<Edge> garbage;
int MST(int cnt,vector<Edge>& E,vector<Edge>& to){
	if(!cnt)
		return 0;
	register int i,ans=0;
	to.clear();
	for(i=0;i<E.size();i++){
		if(!is_same(E[i].u,E[i].v)){
			union_set(E[i].u,E[i].v);
			ans+=E[i].d;
			to.push_back(E[i]);
			if(!(--cnt))
				break;
		}
	}
	return ans;
}

int zb[maxn][2];
inline int EucSqr(int x,int y){
	int t1=zb[x][0]-zb[y][0],t2=zb[x][1]-zb[y][1];
	t1*=t1;
	t2*=t2;
	return t1+t2;
}
int main(){
	int T,q,num,u;
	register int i,j,k,cnt,temp,ans;
	scanf("%d%d",&n,&q);
	for(i=0;i<q;i++){
		scanf("%d%d",&num,&Cost[i]);
		V[i].clear();
		while(num--){
			scanf("%d",&u);
			V[i].push_back(u);
		}
	}
	for(i=1;i<=n;i++){
		scanf("%d%d",&zb[i][0],&zb[i][1]);
	}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++){
			bj.push_back((Edge){i,j,EucSqr(i,j)});
		}
	init_set();
	sort(bj.begin(),bj.end());
	ans=MST(n-1,bj,E);
	for(i=0;i<(1<<q);i++){
		init_set();
		temp=0;
		cnt=n-1;
		for(j=0;j<q;j++)
			if(i&(1<<j)){
				temp+=Cost[j];
				for(k=1;k<V[j].size();k++){
					if(!is_same(V[j][k],V[j][0])){
						union_set(V[j][k],V[j][0]);
						cnt--;
					}
				}
			}
		ans=min(ans,temp+MST(cnt,E,garbage));
	}
	printf("%d\n",ans);
	return 0;
}

[LA 3942]Remember the Word

Trie第一题……

首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~

代码:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int n;
vector<int> AnsList;
namespace Trie{
	const int maxnode=400005;
	const int sigma_siz=26;
	int Tree[maxnode][sigma_siz];
	int val[maxnode];
	int siz;
	inline int idx(char c){
		return c-'a';
	}
	inline void InitTrie(){
		siz=0;
		val[0]=0;
		CL_ARR(Tree[0],0);
	}
	void Insert(char *s,int v){
		register int u=0,n=strlen(s);
		register int i,c;
		REP(i,n){
			c=idx(s[i]);
			if(!Tree[u][c]){
				siz++;
				Tree[u][c]=siz;
				val[siz]=0;
				CL_ARR(Tree[siz],0);
			}
			u=Tree[u][c];
		}
		val[u]=v;
	}
	void Query(char *s,int len){
		register int i,c,u=0;
		AnsList.clear();
		REP(i,len){
			if(!s[i])
				break;
			c=idx(s[i]);
			if(!Tree[u][c])
				break;
			u=Tree[u][c];
			if(val[u])
				AnsList.push_back(val[u]);
		}
	}
};

char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}

[BZOJ 2081]Beads

Hash第一题……

这个题直接枚举串长Hash判断即可。不过,注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣!

代码:

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}

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


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