Postepay как проверить баланс

From Commodious Bird, 3 Years ago, written in Plain Text, viewed 559 times. This paste is a reply to Untitled from 上下界 - go back
URL http://axuhongbo.top/paste/view/a5757bab/diff Embed
Viewing differences between Untitled and Postepay как проверить баланс
#include<bits/stdc++.h>
#define ms(x) memset(x,0,sizeof(x))
using namespace std;
const int inf = 1000000000;
const int maxn = 104100;
const int maxm = 108100;
struct Edge
{
    int v, f, nxt;
};
int src, sink;
int g[maxn + 10];
int nume;
int l, r;
int n, m, k, step = 0;
Edge e[maxm * 2 + 10];
void addedge(int u, int v, int c)
{
    e[++nume].v = v;
    e[nume].f = c;
    e[nume].nxt = g[u];
    g[u] = nume;
    e[++nume].v = u;
    e[nume].f = 0;
    e[nume].nxt = g[v];
    g[v] = nume;
}
void init()
{
    ms(g);
    nume = 1;
}
int x, y;
queue<int>que;
bool vis[maxn+10];
int dist[maxn+10];
void bfs()
{
    ms(dist);
    while(!que.empty()) que.pop();
    vis[src] = true;
    que.push(src);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for(int i=g[u]; i; i=e[i].nxt)
        {
            if(e[i].f && !vis[e[i].v])
            {
                que.push(e[i].v);
                dist[e[i].v] = dist[u] + 1;
                vis[e[i].v] = true;
            }
        }
    }
}
int dfs(int u, int delta)
{
    if(u == sink)
    {
        return delta;
    }
    else
    {
        int ret = 0;
        for(int i=g[u]; delta && i; i = e[i].nxt)
        {
            if(e[i].f && dist[e[i].v] == dist[u] + 1)
            {
                int dd = dfs(e[i].v, min(e[i].f, delta));
                e[i].f -= dd;
                e[i^1].f += dd;
                delta -= dd;
                ret += dd;
            }
        }
        return ret;
    }
}
int maxflow()
{
    int ret = 0;
    while(true)
    {
        ms(vis);
        bfs();
        if(!vis[sink]) return ret;
        ret += dfs(src, inf);
    }
}
int nn,mm;
bool lowbound_flow()
{
    init();
    int s  =n+m+1,t = n+m+2;
    for(int i=0; i<k; i++)
    {

        scanf("%d%d",&x,&y);
        addedge(x,n+y,r-l);

    }
    addedge(t,s,inf);
    int S = n+m+3,T = n+m+4;
    for(int i=1; i<=n; i++)
    {
        //addedge(s,i,r-l);
        addedge(S,i,l);
        addedge(i,T,l);
    }
    for(int i=1; i<=m; i++)
    {
        //addedge(n+i,t,r-l);
        addedge(S,i,l);
        addedge(n+i,T,l);
    }
    src = S;
    sink = T;
    int ans = maxflow();
    if(ans == l*(n+m) )
        return 1;
    else return 0;
}
vector<int>u, v, L, U;
int main()
{

    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {

        scanf("%d%d",&l,&r);
        printf("Case %d: ",++step);
        if(lowbound_flow()) puts("Yes");
        else puts("No");
    }
    return 0;
}

Reply to "Postepay как проверить баланс"

Here you can reply to the paste above

captcha