Codechef Flight

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(LL k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(b-1); k >= (a); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))
#ifdef HOME
#include "debug.h"
#else
#define debug()
#endif
int main()
{
#ifdef HOME
    clock_t start=clock();
    freopen ("in.txt","r",stdin);
    freopen ("out.txt","w",stdout);
    freopen ("out_err.txt","w",stderr);
#endif
    //input gen
    // const int NN=10;
    // cout << 10 << " " << 45 << endl;
    // REP(i,NN)
    // FOR(j,i+1,NN)
    // cout << i << " " << j << " " << rand()%20+1 << endl;
    // return 0;

    int N,M;
    int change=0;
    const int INF=10000;
    cin >> N;
    cin >> M;
    int tmp1,tmp2;
    vector<pair< pair<int,int>,int> > edges(M);
    vector<vector<int> > g(N,vector<int> (N,INF));// node-node -> cost graph
    vector<vector<int> > f(N,vector<int> (N,INF));// node-node -> edge

    REP(i,M)
    {
        cin >> edges[i].first.first >> edges[i].first.second >> edges[i].second;
        edges[i].second*=2;
        g[edges[i].first.first][edges[i].first.second]=edges[i].second;
        g[edges[i].first.second][edges[i].first.first]=edges[i].second;
        f[edges[i].first.first][edges[i].first.second]=i;
        f[edges[i].first.second][edges[i].first.first]=i;
    }

    vector<vector<pair<int,int> > > e(M);//edges -> minimal circle id, sign
    vector<int> m;//minimal circle cost

    REP(i,N)
    {
        //looking for just >i nodes
        // int actual node, vector<int> prev nodes
        typedef pair<int,vector<int> > qType;
        deque<qType> q;
        q.push_back(make_pair(i,vector<int> (1,i)));
        while(q.size())
        {
            int actnode=q.front().first;
            vector<int> actv;
            actv.swap(q.front().second);
            q.pop_front();
            FOR(j,i,N)
            {
                if(actv.size()<3 && j==i)
                    continue;
                if(g[actnode][j]<INF)
                {
                    if(j==i)
                    {//this is an minimal circle yupik
                        //eliminate duplications
                        if(actv[1]>actv.back())
                            break;
                        vector<int> actedges;
                        FOR(k,1,actv.size())
                        {
                            actedges.push_back(f[actv[k-1]][actv[k]]);
                        }
                        actedges.push_back(f[actv.back()][i]);
                        REP(k,actedges.size())
                        {
                            int sumcost=0;
                            REP(t,actedges.size())
                            {
                                if(t==k)
                                    sumcost-=edges[actedges[t]].second;
                                else
                                    sumcost+=edges[actedges[t]].second;
                            }
                            REP(t,actedges.size())
                            {
                                if(t==k)
                                    e[actedges[t]].push_back(make_pair(m.size(),-1));
                                else
                                    e[actedges[t]].push_back(make_pair(m.size(),1));
                            }
                            m.push_back(sumcost);
                        }
                        break;
                    }
                    bool ok=true;
                    FOR(k,1,actv.size()-1)
                    {//contain circle
                        if(g[j][actv[k]]<INF || j==actv[k])
                        {
                            ok=false;
                            break;
                        }
                    }
                    if(!ok)
                        continue;
                    q.push_back(make_pair(j,actv));
                    q.back().second.push_back(j);
                }
            }
        }
    }
    int actualbadcost=0;
    REP(i,m.size())
        if(m[i]<0)
            actualbadcost+=m[i];
    int round=0;
    while(actualbadcost<0)
    {
        ++round;
        int best=-1,bestdir=0,bestimprove=-1;
        REP(i,M)
            for(int j=-1;j<2;j+=2)
                if(edges[i].second+j>0)
                {
                    int improve=0;
                    REP(k,e[i].size())
                    {
                        if(m[e[i][k].first]<0 || (m[e[i][k].first]==0 && e[i][k].second*bestdir<0))
                            improve+=e[i][k].second*j;
                    }
                    if(improve>bestimprove)
                    {
                        best=i;
                        bestdir=j;
                        bestimprove=improve;
                    }
                }
                actualbadcost+=bestimprove;
                edges[best].second+=bestdir;
                REP(k,e[best].size())
                {
                    m[e[best][k].first]+=bestdir*e[best][k].second;
                }
    }
    cout << round/2 << "/1" << endl;
#ifdef HOME
    fprintf(stderr,"time=%.3lfsec\n",0.001*(clock()-start));
#endif
    return 0;
}