2021-team16-dinic

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#pragma GCC optimize("Ofast")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
#define For(i,x,y)  for(ll i=(x);i<=(y);++i)
#define FOr(i,x,y)  for(ll i=(x);i>=(y);--i)
#define rep(i,x,y)  for(ll i=(x);i<(y);++i)
#define clr(a,v)    memset(a,v,sizeof(a))
#define cpy(a,b)    memcpy(a,b,sizeof(a))
#define fi  first
#define se  second
#define pb  push_back
#define mk  make_pair
#define pa  pair<ll,ll>
#define y1  y11111111111111
#define debug   puts("@@@@@@@@@@@@@@@@@@@@@@@")
ll read(){
    ll x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if (ch=='-')    f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())   x=x*10+ch-'0';
    return x*f;
}
void write(ll x){
    if (x<0) putchar('-'),write(-x);
    else{
        if (x>=10)   write(x/10);
        putchar(x%10+'0');
    }
}
const ll N = 1010;
const ll M = 10010;
struct Edge
{
    ll v,c,ne,cost;
}e[M<<1];
ll tot,sink,source,mincost;
ll num[N],x[N];
ll he[N],dep[N];

inline void add(ll u, ll v, ll c, ll cost)
{
    e[tot].v = v; e[tot].c = c;
    e[tot].cost = cost; e[tot].ne = he[u];he[u] = tot++;
}
inline void addedge(ll u, ll v, ll c, ll cost)
{
    add(u,v,c,cost); add(v,u,0,-cost);
}
const ll inf = 0x3f3f3f3f;
ll dis[N],pre[N];
bool vis[N];
inline bool spfa()
{
    queue<ll>q;
    memset(dis,63,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[source] = 0;
    q.push(source);
    while (!q.empty())
    {
        ll cur = q.front(); q.pop();
        vis[cur] = 0;
        for(ll i = he[cur]; i != -1; i = e[i].ne)
        {
            ll to = e[i].v;
            if (e[i].c > 0 && dis[to]>dis[cur]+e[i].cost)
            {
                dis[to] = dis[cur] + e[i].cost;
                if (!vis[to]) {vis[to] = 1; q.push(to);}
            }

        }
    }
    return dis[sink] != inf;
}
inline ll dfs(ll u, ll delta)
{
    if (u == sink) return delta;
    vis[u] = 1;
    ll flow = 0;
    for(ll i = he[u]; i != -1; i = e[i].ne)
    {
        ll to = e[i].v;
        if (!vis[to] && e[i].c > 0 && dis[to] == dis[u] + e[i].cost)
        {
            ll tmp = dfs(to,min(delta-flow,e[i].c));
            if (tmp)
            {
                mincost += e[i].cost * tmp;
                e[i].c -= tmp; e[i^1].c += tmp;
                flow += tmp;
            }
            if(delta==flow)break;//切记不加就被卡到指数级了
         }
    } 
    vis[u] = 0;
    return flow;
}

inline ll dinic()
{
    ll maxflow = 0;
    while (spfa())
    {
        while (1)
        {
            ll tmp = dfs(source,inf);
            if (!tmp) break;
            maxflow += tmp;
        }
    }
    return maxflow;
}

int main()
{



}

/*在edit page界面的代码是正常的*/

#pragma GCC optimize("Ofast")

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#include

using namespace std;

#define ll int

#define ld long double

#define For(i,x,y) for(ll i=(x);i<=(y);++i)

#define FOr(i,x,y) for(ll i=(x);i>=(y);--i)

#define rep(i,x,y) for(ll i=(x);i<(y);++i)

#define clr(a,v) memset(a,v,sizeof(a))

#define cpy(a,b) memcpy(a,b,sizeof(a))

#define fi first

#define se second

#define pb push_back

#define mk make_pair

#define pa pair

#define y1 y11111111111111

#define debug puts("@@@@@@@@@@@@@@@@@@@@@@@")

ll read(){

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

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

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

return x*f;

}

void write(ll x){

if (x<0) putchar('-'),write(-x);

else{

if (x>=10) write(x/10);

putchar(x%10+'0');

}

}

const ll N = 1010;

const ll M = 10010;

struct Edge

{

ll v,c,ne,cost;

}e[M<<1];

ll tot,sink,source,mincost;

ll num[N],x[N];

ll he[N],dep[N];

inline void add(ll u, ll v, ll c, ll cost)

{

e[tot].v = v; e[tot].c = c;

e[tot].cost = cost; e[tot].ne = he[u];he[u] = tot++;

}

inline void addedge(ll u, ll v, ll c, ll cost)

{

add(u,v,c,cost); add(v,u,0,-cost);

}

const ll inf = 0x3f3f3f3f;

ll dis[N],pre[N];

bool vis[N];

inline bool spfa()

{

queueq;

memset(dis,63,sizeof(dis));

memset(vis,0,sizeof(vis));

dis[source] = 0;

q.push(source);

while (!q.empty())

{

ll cur = q.front(); q.pop();

vis[cur] = 0;

for(ll i = he[cur]; i != -1; i = e[i].ne)

{

ll to = e[i].v;

if (e[i].c > 0 && dis[to]>dis[cur]+e[i].cost)

{

dis[to] = dis[cur] + e[i].cost;

if (!vis[to]) {vis[to] = 1; q.push(to);}

}

}

}

return dis[sink] != inf;

}

inline ll dfs(ll u, ll delta)

{

if (u == sink) return delta;

vis[u] = 1;

ll flow = 0;

for(ll i = he[u]; i != -1; i = e[i].ne)

{

ll to = e[i].v;

if (!vis[to] && e[i].c > 0 && dis[to] == dis[u] + e[i].cost)

{

ll tmp = dfs(to,min(delta-flow,e[i].c));

if (tmp)

{

mincost += e[i].cost * tmp;

e[i].c -= tmp; e[i^1].c += tmp;

flow += tmp;

}

if(delta==flow)break;//切记不加就被卡到指数级了

}

}

vis[u] = 0;

return flow;

}

inline ll dinic()

{

ll maxflow = 0;

while (spfa())

{

while (1)

{

ll tmp = dfs(source,inf);

if (!tmp) break;

maxflow += tmp;

}

}

return maxflow;

}

int main()

{

}

/*在edit page界面的代码是正常的*/