poj 2532 坑爹题！！

这题不是坑爹的么！！带宽，带宽不是双向的吗！现在我才反应过来那个alldirectional貌似是定向的意思。。。水题啊！！！！极度水！！灰常水！！你赢了zoj，再也不刷你了！！

ps：网络流也刷的差不多了，开始刷别的了！

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cassert>
using namespace std;


const int inf = 0x3f3f3f3f;
const int maxn = 161;
const int s = 160;

struct zz
{
    int from;
    int to;
    int c;
    int id;
}zx,tz;
vector<zz>g[maxn];
queue<int>q;
int cen[maxn];
int se[maxn];
bool vis[maxn];
int x[maxn*maxn];
int y[maxn*maxn];
vector<int>v;
int n,m,l;

void link(int now,int to,int c,int bc)
{
    zx.from = now;
    zx.to = to;
    zx.c = c;
    zx.id = g[to].size();
    g[now].push_back(zx);
    swap(zx.from,zx.to);
    zx.c = bc;
    zx.id = g[now].size()-1;
    g[to].push_back(zx);
    return ;
}

bool bfs()
{
    while(!q.empty())
    {
        q.pop();
    }
    memset(cen,-1,sizeof(cen));
    q.push(s);
    cen[s] = 0;
    int now,to;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(int i=0;i<g[now].size();i++)
        {
            to = g[now][i].to;
            if(g[now][i].c > 0 && cen[to] == -1)
            {
                cen[to]=cen[now]+1;
                q.push(to);
            }
        }
    }
    return cen[0] != -1;
}

int dfs(int flow = inf,int now = s)
{
    if(now == 0)
    {
        return flow;
    }
    int temp,sum =0;
    int to;
    for(int i=0;i<g[now].size();i++)
    {
        to = g[now][i].to;
        if(g[now][i].c>0 && flow>sum && cen[now]+1 == cen[to])
        {
            temp = dfs(min(flow-sum,g[now][i].c),to);
            sum += temp;
            g[now][i].c -= temp;
            g[to][g[now][i].id].c += temp;
        }
    }
    if(!sum) cen[now] = -1;
    return sum;
}

void dinic()
{
    while(bfs())
    {
       dfs();
    }
    return ;
}

void bfss()
{
    while(!q.empty())
    {
        q.pop();
    }
    memset(se,0,sizeof(se));
    memset(vis,false,sizeof(vis));
    q.push(s);
    vis[s] = true;
    se[s] = 1;
    int now,to;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(int i=0;i<g[now].size();i++)
        {
            to = g[now][i].to;
            if(g[now][i].c > 0)
            {
                se[to] = 1;
                if(!vis[to])
                {
                    vis[to] = true;
                    q.push(to);
                }
            }
        }
    }
    return ;
}

void bfst()
{
    while(!q.empty())
    {
        q.pop();
    }
    memset(vis,false,sizeof(vis));
    vis[0] = true;
    se[0] = 2;
    q.push(0);
    int now,from,id;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(int i=0;i<g[now].size();i++)
        {
            id = g[now][i].id;
            from = g[now][i].to;
            if(g[from][id].c > 0)
            {
                se[from] = 2;
                if(!vis[from])
                {
                    vis[from] = true;
                    q.push(from);
                }
            }
        }
    }
    return ;
}

void zz1215()
{
    dinic();
    bfss();
    bfst();
    v.clear();
    for(int i=1;i<=l;i++)
    {
        if(se[x[i]] == 1 && se[y[i]]==2)
        {
           v.push_back(i);
        }
    }
    if(v.empty())
    {
        cout<<endl;
    }
    else
    {
        cout<<v[0];
        for(int i=1;i<v.size();i++)
        {
            cout<<" "<<v[i];
        }
        cout<<endl;
    }
    return ;
}

int main()
{
    while(cin>>n)
    {
        if(n==0)
        {
            break;
        }
        cin>>m>>l;
        for(int i=0;i<maxn;i++)
        {
            g[i].clear();
        }
        int c;
        for(int i=1;i<=l;i++)
        {
            cin>>x[i]>>y[i]>>c;
            link(x[i],y[i],c,0);
        }
        for(int i=1;i<=n;i++)
        {
            link(s,i,inf,0);
        }
        zz1215();
    }
     return 0;
}