记录编号	590723	评测结果	AAAA
题目名称	[ZOJ 2676]网络战争	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2024-07-10 23:08:08	内存使用	3.56 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define db double
#define in inline
#define re register
#define F(i,a,b) for(int i = a;i <= b;i++)
#define D(i,a,b) for(int i = a;i >= b;i--)
const int N = 510,M = 5010;
const double eps = 1e-9,inf = 1e8;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<3) + (x<<1) + c-'0';
    return x * f;
}

int n,m,s,t;
struct made{
    int ver,nx;db ed;int id;
};
struct flow{
    made e[M*10];
    int hd[N],tot = 1;
    in void add(int x,int y,db z,int id){
        e[++tot] = {y,hd[x],z,id},hd[x] = tot;
        e[++tot] = {x,hd[y],z,id},hd[y] = tot;//双向边 
    }
    int d[N],cur[N];
    in db dinic(int x,db fl){
        if(x == t)return fl;
        db rest = fl;
        for(re int i = cur[x];i && fabs(rest) > eps;i = e[i].nx){
            int y = e[i].ver;cur[x] = i;// 
            if(fabs(e[i].ed) > eps && d[y] == d[x] + 1){
                db c = dinic(y,min(rest,e[i].ed));
                if(fabs(c) < eps)d[y] = 0;
                e[i].ed -= c,e[i^1].ed += c;
                rest -= c;
            }
        }
        return fl - rest;
    }
    in db bfs(){
        db ans = 0;
        while(1){
            memset(d,0,sizeof d);
            memcpy(cur,hd,sizeof hd);
            queue<int>q;
            q.push(s);q.push(s),d[s] = 1;
            while(!q.empty()){
                int x = q.front();q.pop();
                for(re int i = hd[x];i;i = e[i].nx){
                    int y = e[i].ver;
                    if(fabs(e[i].ed) > eps && !d[y])d[y] = d[x] + 1,q.push(y);
                }
            }//分层图 
            if(!d[t])return ans;
            ans += dinic(s,inf);//多路增广 
        }
    }
}f;



struct node{
    int x,y; db v;
}a[M];
in bool check(double mid){
    f.tot = 1;
    db s = 0;
    memset(f.hd,0,sizeof f.hd);
    for(int i = 1;i <= m;i++){
        if(a[i].v + eps <= mid)s += a[i].v - mid;
        else f.add(a[i].x,a[i].y,a[i].v - mid,i);
    }
    s += f.bfs();
    return s < -eps;
}


vector<int>ans; 
bool v[N];
void dfs(int x){
	if(v[x])return;
	v[x] = 1;
	for(int i = f.hd[x];i;i = f.e[i].nx){
		int y = f.e[i].ver;
		if(fabs(f.e[i].ed) > eps)dfs(y);
	}	
}
int main(){
    freopen("networkwar.in","r",stdin);
    freopen("networkwar.out","w",stdout);
	while(n = read(),m = read()){
		if(!n)break;
		s = 1,t = n;
	    for(int i = 1;i <= m;i++)a[i].x = read(),a[i].y = read(),a[i].v = read();
	    //
	    double l = 0,r = 1e5;
	    while(l + eps < r){
	        double mid = (l + r) / 2;
	        if(check(mid))r = mid;
	        else l = mid;
	    }
//	    printf("%lf\n",l + eps);
   		memset(v,0,sizeof v);
		dfs(s);	
	    ans.clear();
		for(int i = 1;i <= m;i++)
		    if(v[a[i].x] != v[a[i].y] || a[i].v <= l + eps)ans.push_back(i);
	    sort(ans.begin(),ans.end());
	    printf("%d\n",ans.size());
	    for(int i = 0;i < ans.size();i++)printf("%d ",ans[i]);
	    printf("\n\n");
	}


    return cerr<<endl<<"Time:"<<clock()<<"ms"<<endl,0;
     
}