[TJOI2014] 匹配

注：此题无序，也无嵬

正文

我们这题求得事实上是一个最大费用最大流，最后的对每条边进行枚举，额然后，如果最大费用小了，就计入答案。。

算是，比较水吧

还有，一开始WA了两次是因为，dis应初始化为负无穷

/* make by ltao */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <fstream>
#include <math.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <string>
#include <complex>
#include <sstream>
#include <set>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define sz 666666
#define fake int
#define re return
#define get() getchar()
#define inf 1e6
#define diss(i) dis[i]+h[i]
using namespace std;
int read(){
    int x=0;bool f=0;
    char ch=get();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=get();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=get();
    }
    return f?-x:x;
}
const int Maxn=81;
#define Maxx 2*Maxn
#define Maxm Maxn*Maxn*2
int n,cnt,s,t,maxflow,maxcost,h[Maxx],dis[Maxx],cur[Maxx],a[Maxx];
bool vis[Maxx];
struct Edge{
    int to,lac,flow,cost;
    bool can;
    void insert(int x,int y,int z,int w){
        to=y;lac=h[x];flow=z;cost=w;h[x]=cnt++;
    }
}edge[Maxm],vedge[Maxm];
void add_edge(int x,int y,int z,int w){
    vedge[cnt].insert(x,y,z,w);
    vedge[cnt].insert(y,x,0,-w);
}
int val=-1;
bool spfa(int s,int t){
    for(int i=1;i<=t;i++) dis[i]=-0x3f3f3f3f;
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    dis[s]=0;vis[s]=1;q.push(s);
    while(!q.empty()){
        int fr=q.front();
        vis[fr]=0;
        q.pop();
        for(int i=h[fr];i!=-1;i=edge[i].lac){
            int to=edge[i].to;
            if(edge[i].flow>0&&!edge[i].can&&dis[to]<dis[fr]+edge[i].cost){
                dis[to]=dis[fr]+edge[i].cost;
                if(!vis[to]){
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
    }
    return dis[t]!=-0x3f3f3f3f;
}
int dfs(int u,int min1){
    if(u==t) return min1;
    int sum=min1;vis[u]=1;
    for(int i=cur[u];i!=-1;i=edge[i].lac){
        int to=edge[i].to;
        if(!vis[to]&&!edge[i].can&&dis[to]==dis[u]+edge[i].cost&&edge[i].flow>0){
            cur[u]=i;
            int ret=dfs(to,min(sum,edge[i].flow));
            sum-=ret;edge[i].flow-=ret;edge[i^1].flow+=ret;
            if(sum==0) break;
        }
    }
    vis[u]=0;
    return min1-sum;
}
void Dinic(int s,int t){
    while(spfa(s,t)){
        int ret=dfs(s,0x3f3f3f3f);
        maxflow+=ret;
        maxcost+=ret*dis[t];
    }
    re ;
}
int main(){
    freopen("YJOI2016.in","r",stdin);
    n=read();
    s=0;t=n<<1|1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) add_edge(s,i,1,0);
    for(int j=n+1;j<=n<<1;j++) add_edge(j,t,1,0);
    for(int i=1;i<=n;i++) for(int j=n+1;j<=n*2;j++) add_edge(i,j,1,read());
    memcpy(edge,vedge,sizeof edge);
    Dinic(s,t);
    int cnt1=0;
    for(int i=0;i<cnt;i++){
        int to=edge[i].to,fr=edge[i^1].to;
        if(!edge[i].flow&&fr<=n&&fr>=1&&to>n&&to<=n*2)
            a[++cnt1]=i;
    }
    printf("%d\n",maxcost);
    int max1=maxcost;
    for(int i=1;i<=cnt1;i++){
        memcpy(edge,vedge,sizeof edge);
        edge[a[i]].can=1;
        edge[a[i]^1].can=1;
        maxflow=0;
        maxcost=0;
        Dinic(s,t);
        if(maxflow==n&&maxcost!=max1)
            printf("%d %d\n",edge[a[i]^1].to,edge[a[i]].to-n);
        edge[a[i]].can=0;
        edge[a[i]^1].can=0;
    }
    re 0;
}

我看到有人拿km写的，算了，我还是好好用费用流吧，，，

巴特西

[TJOI2014] 匹配

正文

最新文章

热门文章