респа 2007 второй тур - "крестики-нолики 2007"

#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;
#define N 222
#define M 22222

char c[N][N];
int n,m,C,ef[M],es[M],ev[M],first[N],next[M],S=161,T=162,k1[N],k2[N],k[N],from[N],edge[N];
bool b[N];

void _add(int x,int y,int z){
    next[++C]=first[x];first[x]=C;
    ef[C]=x;es[C]=y;ev[C]=z;
}

int be(int x){
    return (x&1)?x+1:x-1;
}

void add(int x,int y,int z){
    _add(x,y,z);_add(y,x,0);
}

void input(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%c",&c[i][j]);
        scanf("\n");
    }
}

void init(){
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (c[i][j]=='?' || c[i][j]=='-') ++k1[i];
            else if (c[i][j]=='+') ++k2[i];
    for (int i=1;i<=n;i++) k[i]=(k1[i]+k2[i])/2-k2[i];
    for (int i=1;i<=n;i++) add(S,i,k[i]);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (c[i][j]=='?') add(i,80+j,1);
    memset(k1,0,sizeof(k1));memset(k2,0,sizeof(k2));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (c[i][j]=='?' || c[i][j]=='-') ++k1[j];
            else if (c[i][j]=='+') ++k2[j];
    for (int i=1;i<=m;i++) k[i]=(k1[i]+k2[i])/2-k2[i];
    for (int i=1;i<=m;i++) add(i+80,T,k[i]);
}

bool flow(){
    queue<int> q;memset(b,0,sizeof(b));
    b[S]=1;q.push(S);
    while (!q.empty()){
        int v=q.front();q.pop();
        for (int h=first[v];h;h=next[h])
            if (!b[es[h]] && ev[h]>=1){
                b[es[h]]=1;
                from[es[h]]=v;
                edge[es[h]]=h;
                q.push(es[h]);
                if (es[h]==T) return 1;
            }
    }
    return 0;
}

void print(){
    for (int i=1;i<=C;i++)
        if (ef[i]>=1 && ef[i]<=n && es[i]>80){
            if (ev[i]==0) c[ef[i]][es[i]-80]='+';
            else c[ef[i]][es[i]-80]='-';
        }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) printf("%c",c[i][j]);
        printf("\n");
    }
}

int main(){
    input();
    init();
    while (flow()){
        int mn=1<<30;
        for (int h=T;h!=S;h=from[h]) mn=min(mn,ev[edge[h]]);
        for (int h=T;h!=S;h=from[h]){
            ev[edge[h]]-=mn;
            ev[be(edge[h])]+=mn;
        }
    }
    print();
    return 0;
}