记录编号	310316	评测结果	AAAA
题目名称	[ZOJ 2676]网络战争	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.256 s
提交时间	2016-09-22 10:30:16	内存使用	0.24 MiB

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

const int maxn=150;
const double eps=1e-6;
const int INF=2147483647;

struct Edge{
    double flow;
    int from,to,cap;

    Edge(int u=0,int v=0,int w=0):from(u),to(v),cap(w),flow(0) {}
};

template<class T> inline bool getd(T& x)
{
    int ch=getchar();
    bool neg=false;
    while(ch!=EOF && ch!='-' && !isdigit(ch)) ch=getchar();
    if(ch==EOF) return false;
    if(ch=='-'){
        neg=true;
        ch=getchar();
    }
    x=ch-'0';
    while(isdigit(ch=getchar())) x=x*10+ch-'0';
    if(neg) x=-x;
    return true;
}

double R;
queue<int> q;
vector<Edge> edges;
vector<int> G[maxn];
bool ins[maxn],ok=false;
int n,m,maxR,s,t,dist[maxn],cur[maxn];

void AddEdge(int from,int to,int cap){
    edges.push_back(Edge(from,to,cap));
    edges.push_back(Edge(to,from,0));
    int m1=edges.size();
    G[from].push_back(m1-2);
    G[to].push_back(m1-1);
}

bool bfs()
{
    for(int i=1;i<=n;i++) dist[i]=INF;
    dist[s]=0;
    q.push(s);

    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            Edge e=edges[G[u][i]];
            if(e.cap-e.flow-R>eps && dist[e.to]==INF){
            	dist[e.to]=dist[u]+1;
            	q.push(e.to);
            }
        }
    }
    if(dist[t]==INF) return false;
    return true;
}

double dfs(int u,double a)
{
    double f,flow=0;
    if(u==t || a<eps) return a;
    for(int& i=cur[u];i<G[u].size();i++){
        Edge& e=edges[G[u][i]];
        if(dist[u]+1==dist[e.to] && e.cap-e.flow-R>eps && (f=dfs(e.to,min(a,e.cap-e.flow-R)))>eps){
           flow+=f;
           e.flow+=f;
           edges[G[u][i]^1].flow-=f;
           a-=f;
           if(a<eps) return flow;
        }
    }
    return flow;
}

void finds(int u)
{
    ins[u]=true;
    for(int i=0;i<G[u].size();i++){
        Edge e=edges[G[u][i]];
//        printf("from=%d,to=%d,cap=%d,R=%lf,flow=%lf\n",e.from,e.to,e.cap,R,e.flow);
        if(e.cap-e.flow-R>eps && !ins[e.to]) finds(e.to);
    }
}

double judge()
{
    double ans=0;
    for(int i=0;i<edges.size();i++){
        edges[i].flow=0;
        if(i%2==0 && edges[i].cap-R<eps) ans+=edges[i].cap-R;
    }
    while(bfs()){
        memset(cur,0,sizeof(cur));
        ans+=dfs(1,INF);
    }
    return ans;
}

void init()
{
    s=1;t=n;
    maxR=0;
    edges.clear();
    memset(ins,false,sizeof(ins));
    for(int i=0;i<maxn;i++) G[i].clear();

    for(int i=0;i<m;i++){
        int from,to,cap;
        getd(from);getd(to);getd(cap);
        AddEdge(from,to,cap);
        maxR+=cap;
    }
}

void work()
{
    double l=0,r=maxR>0?maxR:INF;
    while(r-l>eps){
        R=(l+r)/2;
        if(judge()<0) r=R;
        else l=R;
    }
//	printf("R=%lf\n",R);

    finds(s);
    int number=0;
    /*
    for(int i=1;i<=n;i++) printf("%d ",ins[i]);
	cout<<endl;
	//输出中间结果 
	*/
    for(int i=0;i<edges.size();i+=2){
        Edge e=edges[i];
        if((ins[e.to] xor ins[e.from]) || e.cap-R<-eps) number++;
    }
    printf("%d\n",number);
    for(int i=0;i<edges.size();i+=2){
        Edge e=edges[i];
        if((ins[e.to] xor ins[e.from]) || e.cap-R<-eps) {
            number--;
            if(number) printf("%d ",i/2+1);
            else printf("%d\n",i/2+1);
        }
    }
}

int main()
{
    freopen("networkwar.in","r",stdin);
    freopen("networkwar.out","w",stdout);
    while(getd(n) && getd(m) && n && m){
    	if(ok) printf("\n");
		ok=true;
        init();
        work();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}