UOJ Logo ZH_comld的博客

博客

新博客

2019-01-27 20:57:09 By ZH_comld
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#include<queue>
#define inf 2e9
#define N 100006
#define M 20000009
using namespace std;
typedef long long ll;
queue<int>q;
int head[N],tot=1,top,dis[N],id1[1000][1000],id2[1000][1000],fl[N],pre[N],vv[N],uu[N],n,m,k,du[1002],opt,idd[N];
ll ans;
bool vis[N];
inline int rd(){
    int x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
struct edge{int n,to,l,f;}e[M];
inline void add(int u,int v,int l,int f){
    cout<<u<<" "<<v<<" "<<l<<" "<<f<<endl;
    e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;e[tot].f=f;
    e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;e[tot].f=-f;
}
bool spfa(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;q.push(s);fl[s]=inf;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=1;
        for(int i=head[u];i;i=e[i].n){
            int v=e[i].to;
            if(e[i].l&&dis[v]>dis[u]+e[i].f){
                dis[v]=dis[u]+e[i].f;
                pre[v]=u;fl[v]=min(fl[u],e[i].l);
                if(!vis[v]){vis[v]=1;q.push(v);}
            }
        }
    }
    return dis[t]!=0x3f3f3f3f;
}
void calc(int s,int t){
    int x=t;
    while(x!=s){
        int i=pre[x];
        e[i].l-=fl[t];e[i^1].l+=fl[t];
        x=e[i^1].to;
    }
    ans+=fl[t]*dis[t];
}
int main(){
    freopen("placement.in","r",stdin);
    //freopen("placement.out","w",stdout);
    n=rd();m=rd();k=rd();opt=rd();int u,v;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=k;++j){
            id1[i][j]=++top,id2[i][j]=++top;
        }
    for(int i=1;i<=k;++i)idd[i]=++top;
    for(int i=1;i<=m;++i){
        uu[i]=rd();vv[i]=rd();du[uu[i]]++;
    }
    for(int i=1;i<=k;++i){
       if(!du[i]){
           for(int j=1;j<=n;++j)add(0,id1[j][i],1,0);
       }
       for(int j=1;j<=n;++j)add(id2[j][i],idd[i],1,0);
    }
    for(int i=1;i<=k;++i)add(idd[i],top+1,1,0);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=k;++j){
            u=rd();add(id1[i][j],id2[i][j],1,u);
        }
    for(int i=1;i<=k;++i)
        for(int j=1;j<=k;++j){
            u=rd();
            for(int o=1;o<=m;++o){
                add(id2[i][vv[o]],id1[j][uu[o]],1,u);
            }
        }
    while(spfa(0,top+1))calc(0,top+1);
    cout<<ans;
    fclose(stdin);fclose(stdout);
    return 0;
}

评论

alalala0830
前排资瓷!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。