sxczf's Blog

用网络流做的哦

题目就不发了……

内存看太大莫名TLE……

/**************************************************************
    Problem: 1000
    User: czfsycjsb
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:820 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
#define maxlongint 2147483647
#define maxn 105
#define maxm 1005
using namespace std;
int a,b,c,d,e,g,h,i,j,k,l,m,n,ans,dis[maxn],flag,S,T,tot;
int way[maxm],last[maxn],next[maxm],cost[maxm];
int min(int a,int b){if (a<b)return a;return b;}
void spfa(){
     int now,head,tail,dl[maxn],flag[maxn];
     memset(dis,0x7f,sizeof(dis));
     memset(flag,0,sizeof(flag));
     head=1;tail=1;dis[S]=0;dl[1]=S;
     for (;head<=tail;++head){
         now=dl[head];
         flag[now]=1;
         for (int i=last[now];i;i=next[i])
         if ((cost[i])&&(dis[way[i]]>dis[now]+1)){
                    dis[way[i]]=dis[now]+1;
                    if (!flag[way[i]]){dl[++tail]=way[i];flag[way[i]]=1;}
             }
         }
     }
int dfs(int x,int flow){
    if (flow==0)return 0;
    if (x==T){flag=1;return flow;}
    int sum=0,tmp=0;
    for (int i=last[x];i;i=next[i])
    if (dis[way[i]]==dis[x]+1){
                                  tmp=dfs(way[i],min(flow-sum,cost[i]));
                                  sum+=tmp;
                                  cost[i]-=tmp;
                                  cost[i^1]+=tmp;
                                  if (sum>=flow)return flow;
                                  }
       return sum;
}
inline void make(int a,int b,int c){
    way[++tot]=b;
    next[tot]=last[a];
    last[a]=tot;
    cost[tot]=c;
    way[++tot]=a;
    next[tot]=last[b];
    last[b]=tot;
    cost[tot]=0;
}
int main(){
    tot=1;
    scanf("%d%d",&n,&m);
    make(1,2,n+m);
    S=1;T=2;
    flag=1;
    for (;flag;){
        spfa();
        flag=0;
        ans+=dfs(S,maxlongint);
        }
    printf("%d\n",ans);
    return 0;
}