(UVA) 259 - Software Allocation

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=195

flow !

Note that the code is not the AC code(due to EOF issue)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 106;
const int INF = 1e9 + 7;

struct Edge {
    int to,cap,rev;
};

vector<Edge> edg[MAX_N];
int iter[MAX_N];
int level[MAX_N];
int ans[MAX_N];

void add_edge(int from,int to,int cap) {
    edg[from].push_back((Edge){to,cap,edg[to].size()});
    edg[to].push_back((Edge){from,0,edg[from].size()-1});
}

void BFS(int s) {
    memset(level,-1,sizeof(level));
    level[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        int len=edg[t].size();
        for (int i=0;len>i;i++) {
            Edge &tmp=edg[t][i];
            if (tmp.cap >0 && level[tmp.to] < 0) {
                level[tmp.to] = level[t] + 1;
                que.push(tmp.to);
            }
        }
    }
}

int DFS(int v,int t,int f,int source) {
    if (v==t) return f;
    int len = edg[v].size();
    for (int &i=iter[v];i<len;i++) {
        Edge &tmp=edg[v][i];
        if (tmp.cap > 0 && level[v] < level[tmp.to]) {
            int d=DFS(tmp.to,t,min(f,tmp.cap),v);
            if (d>0) {
                tmp.cap -= d;
                edg[tmp.to][tmp.rev].cap += d;
                if ('0' <= v &&  v <= '9') {
                    ans[v] = source;
                }
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int s,int t) {
    int flow=0;
    while (true) {
        BFS(s);
        if (level[t] < 0) break;
        memset(iter,0,sizeof(iter));
        int f;
        while ((f=DFS(s,t,INF,s)) > 0) {
            flow += f;
        }
    }
    return flow;
}

vector<string> v;

int main () {
    //freopen("output.txt","w",stdout);
    string s;
    while (getline(cin,s)) {
        if (s=="") {
            memset(ans,0,sizeof(ans));
            for (int x=0;MAX_N>x;x++) {
                edg[x].clear();
            }
            int sum=0;
            for (vector<string>::iterator iter=v.begin();iter!=v.end();iter++) {
                s=*iter;
                char c=s[0];
                int t=s[1]-'0';
                sum += t;
                add_edge(0,c,t);
                int tmp=3;
                while (s[tmp] != ';') {
                    add_edge(c,s[tmp],1);
                    //add_edge(s[tmp],1,1);
                    tmp++;
                }
            }
            for (int x='0';'9'>=x;x++) {
                add_edge(x,1,1);
            }
            //cout<<"innnn\n";
            int ret = Dinic(0,1);
            //cout<<"ret = "<<ret<<endl;
            if (ret == sum) {
                for (int x='0';'9'>=x;x++) {
                    printf("%c",(ans[x]==0?'_':char(ans[x])));
                }
                puts("");
            }
            else {
                puts("!");
            }
            v.clear();
        }
        else {
            v.push_back(s);
        }
    }
}