[CodeChef]RIN（最小割）

Description

有m门课可以在n个学期内学习，第i门课在第j个学期的收益是\(X_{i,j}\),一个学期可以学多门课，有的课之间有依赖关系，即必须先学a再学b，求最大收益。n,m<=100

Solution

对于\(X_{i,j}\)建成一条一条边表示流量，此时最小割为最小收益

这里收益最大为100，可以将\(X_{i,j}\)建成\(100-X_{i,j}\)即损失的收益，然后跑最小割就是最少损失的收益，用n*100减去就是答案了

对于一个限制条件（a,b），对于所有i连边，\(X_{a,i}\)连向\(X_{b,i+1}\)，容量为无穷大

此时这条边永远不会被割，可满足限制条件

Code

#include <cstdio>

#include <algorithm>

#define N 200010

#define Inf 0x7fffffff

using namespace std;

struct info{int to,nex,f;}e[N];

int n,m,k,T,S,tot,nodes,head[10010],Ans,cnt[10010],dis[10010];

inline void Link(int u,int v,int f){

    e[++tot].to=v;e[tot].nex=head[u];head[u]=tot;e[tot].f=f;

    e[++tot].to=u;e[tot].nex=head[v];head[v]=tot;e[tot].f=0;

}

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline void Init(){

    n=read(),m=read(),k=read();

    S=0,tot=1,nodes=(T=n*m+1)+1;

   	for(int i=1;i<=n;++i)

   		for(int j=1;j<=m;++j){

   			int t=read();

   			Link((i-1)*m+j,(j==m)?T:(i-1)*m+j+1,(t==-1)?Inf:100-t);

		}

	for(int i=1;i<=n;++i) Link(S,(i-1)*m+1,Inf);

	while(k--){

		int u=read(),v=read();

		for(int i=1;i<=m;++i) Link((u-1)*m+i,(i==m)?T:(v-1)*m+i+1,Inf);

	}

}

int sap(int u,int d){

    if(u==T) return d;

    int sum=0,mins=nodes;

    for(int i=head[u];i;i=e[i].nex){

        int v=e[i].to;

        if(e[i].f>0&&dis[u]==dis[v]+1){

            int save=sap(v,min(d-sum,e[i].f));

            sum+=save;

            e[i].f-=save;

            e[i^1].f+=save;

            if(dis[S]>=nodes||sum==d) return sum;

        }

        if(e[i].f>0) mins=min(mins,dis[v]);

    }

    if(!sum){

        if(!(--cnt[dis[u]])) dis[S]=nodes;

        else ++cnt[dis[u]=mins+1];

    }

    return sum;

}

void SAP(){cnt[0]=nodes;while(dis[S]<nodes) Ans+=sap(S,Inf);}

int main(){

    Init();

    SAP();

    double AAA=(n*100-Ans)*1.0/n;

    printf("%.2lf\n",AAA);

    return 0;

}

巴特西

[CodeChef]RIN（最小割）

Description

Solution

Code

最新文章

热门文章