NKNET - Mạng truyền tin
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 111
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi first
#define se second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
class DinicFlow {
private:
vector<int> dist,head,q,work;
vector<int> capa,flow,next,point;
int n,m;
public:
DinicFlow() {
n=0;m=0;
}
DinicFlow(int n,int _m) {
this->n=n;
this->m=0;
dist=vector<int>(n+7);
head=vector<int>(n+7,-1);
q=vector<int>(n+7);
work=vector<int>(n+7);
int m=2*_m;
capa=vector<int>(m+7);
flow=vector<int>(m+7,0);
next=vector<int>(m+7);
point=vector<int>(m+7);
}
void addedge(int u,int v,int c1,int c2) {
point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++;
point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++;
}
bool bfs(int s,int t) {
FORE(it,dist) *it=-1;
int sz=1;
q[0]=s;dist[s]=0;
REP(x,sz) {
int u=q[x];
for (int i=head[u];i>=0;i=next[i])
if (dist[point[i]]<0 && flow[i]<capa[i]) {
dist[point[i]]=dist[u]+1;
q[sz]=point[i];
sz++;
}
}
return (dist[t]>=0);
}
int dfs(int s,int t,int f) {
if (s==t) return (f);
for (int &i=work[s];i>=0;i=next[i])
if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
if (d>0) {
flow[i]+=d;
flow[i^1]-=d;
return (d);
}
}
return (0);
}
int maxflow(int s,int t,vector<int> &v) {
int ret=0;
while (bfs(s,t)) {
FOR(i,1,n) work[i]=head[i];
while (true) {
int d=dfs(s,t,INF);
if (d<=0) break;
ret+=d;
}
}
v.clear();
FOR(i,1,n) if (dist[i]>=0) v.push_back(i);
//printf("MaxFlow %d\n",ret);
return (ret);
}
};
vector<ii> g[MAX];
int d[MAX];
bool src[MAX];
int n,m,s,t;
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
REP(i,m) {
int u,v,c;
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&c);
g[u].push_back(ii(v,c));
g[v].push_back(ii(u,c));
}
scanf("%d",&s);
scanf("%d",&t);
}
bool bfs(int s,int t,int x) {
queue<int> q;
while (!q.empty()) q.pop();
memset(d,-1,sizeof d);
q.push(s);
d[s]=0;
while (!q.empty()) {
int u=q.front();q.pop();
if (u==t) return (true);
FORE(it,g[u]) if (it->se>x) {
int v=it->fi;
if (d[v]<0) {
d[v]=d[u]+1;
q.push(v);
}
}
}
return (false);
}
int findtime(void) {
int l=0;
int r=INF;
while (true) {
if (l==r) return (r);
if (r-l==1) {
if (!bfs(s,t,l)) return (l);
else return (r);
}
int m=(l+r)>>1;
if (!bfs(s,t,m)) r=m;
else l=m+1;
}
}
void process(void) {
int ans=findtime();
DinicFlow G=DinicFlow(n,m);
FOR(i,1,n) FORE(it,g[i]) {
int j=it->fi;
int cst;
if (it->se<=ans) cst=1; else cst=INF;
if (i<j) G.addedge(i,j,cst,cst);
}
vector<int> v;
vector<ii> res;
assert(G.maxflow(s,t,v)<INF);
FORE(it,v) src[*it]=true;
FORE(it,v) FORE(jt,g[*it]) if (!src[jt->fi]) res.push_back(ii(*it,jt->fi));
printf("%d\n",res.size());
FORE(it,res) printf("%d %d\n",it->fi,it->se);
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.txt","r",stdin);
printf("START\n");
#endif
loadgraph();
process();
return 0;
}