一道很果的最大流，需要自己建个超级源和超级汇
先是EKarp
756K
594MS 1373B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N= 110;
int n;
int mat[N][N];
int EKarp(int s, int t)
{
queue < int > que;
int flow[N][N], pre[N], temp[N], u, v, sum= 0;
memset(flow, 0 , sizeof(flow));
while (1)
{
que.push(s);
memset(temp, 0, sizeof(temp));
temp[s]= 0x7fffffff;
while ( ! que.empty() )
{
u= que.front();
que.pop();
for ( v= 0 ; v < n+2 ; v++ )
if ( !temp[v] && mat[u][v] > flow[u][v] )
{
que.push(v);
temp[v]= temp[u] < mat[u][v]-flow[u][v] ? temp[u] : mat[u][v]-flow[u][v];
pre[v]= u;
}
}
if ( temp[t] == 0 )
break;
for ( u = t ; u != s ; u=pre[u] )
{
flow[pre[u]][u] += temp[t];
flow[u][pre[u]] -= temp[t];
}
sum+= temp[t];
}
return sum;
}
int main()
{
while ( EOF != scanf("%d", &n) )
{
memset(mat, 0, sizeof(mat));
int i, source, user, nodes;
scanf("%d%d%d", &source, &user, &nodes);
int s, e, t;
for ( i = 0 ; i < nodes ; i++ )
{
scanf("%*[^(](%d,%d)%d", &s, &e, &t);
mat[s][e]=t;
}
for ( i = 0 ; i < source ; i++ )
{
scanf("%*[^(](%d)%d", &e, &t);
mat[n][e]= t;
}
for ( i = 0 ; i < user ; i++ )
{
scanf("%*[^(](%d)%d", &s, &t);
mat[s][n+1]= t;
}
printf("%d\n", EKarp(n, n+1));
}
return 0;
}
然后是STL队列的dinic
724K 79MS 1904B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N= 110;
int n;
int mat[N][N];
int lev[N];
queue<int> q;
int BFS(int s,int t)
{
int u,v;
memset(lev,-1,sizeof(lev));
q.push(s);
lev[s] = 0;
while( !q.empty() )
{
u = q.front();
q.pop();
for(v=0; v<=t; v++)
if( mat[u][v] > 0 && lev[v] == -1 )
{
lev[v] = lev[u] + 1;
q.push(v);
}
}
return lev[t] != -1;
}
int Dinic(int s,int t)
{
int a[N],cur[N];
int pre[N];
int flow = 0;
int i,u,flag,v,ag,k;
while( BFS(s,t) )
{
for(i=0; i<=t; i++)
{
cur[i] = 0;
a[i] = 0x7fffffff;
}
u = s;
while(1)
{
flag = 0;
for(v=cur[u]; v<=t; v++)
if( mat[u][v] > 0 && lev[u] + 1 == lev[v] )
{
flag = 1;
break;
}
if( flag )
{
cur[u] = v + 1;
pre[v] = u;
a[v] = mat[u][v];
if( a[v] > a[u] )
a[v] = a[u];
u = v;
if( u == t )
{
ag = a[t];
flow += ag;
for(v=t; v!=s; v=pre[v])
{
cur[pre[v]] = v;
mat[pre[v]][v] -= ag;
mat[v][pre[v]] += ag;
a[v] -= ag;
if( mat[pre[v]][v] == 0 )
u = pre[v];
}
}
}
else
if( u != s )
{
lev[u] = 0x7fffffff;
u = pre[u];
}
else break;
}
}
return flow;
}
int main()
{
while ( EOF != scanf("%d", &n) )
{
memset(mat, 0, sizeof(mat));
int i, source, user, nodes;
scanf("%d%d%d", &source, &user, &nodes);
int s, e, t;
for ( i = 0 ; i < nodes ; i++ )
{
scanf("%*[^(](%d,%d)%d", &s, &e, &t);
mat[s][e]=t;
}
for ( i = 0 ; i < source ; i++ )
{
scanf("%*[^(](%d)%d", &e, &t);
mat[n][e]= t;
}
for ( i = 0 ; i < user ; i++ )
{
scanf("%*[^(](%d)%d", &s, &t);
mat[s][n+1]= t;
}
printf("%d\n", Dinic(n, n+1));
}
return 0;
}
最后是最强大的手写队列dinic
416K 63MS 1890B
#include <stdio.h>
#include <string.h>
const int N= 110;
const int MAX_QUE= 1<<15;
int n;
int mat[N][N];
int lev[N], que[MAX_QUE];
int BFS(int s,int t)
{
int u,v;
int front= 1, rear= 0;
memset(lev,-1,sizeof(lev));
que[0]= s;
lev[s] = 0;
while( front > rear )
{
u = que[rear++];
for(v=0; v<=t; v++)
if( mat[u][v] > 0 && lev[v] == -1 )
{
lev[v] = lev[u] + 1;
que[front++]= v;
}
}
return lev[t] != -1;
}
int Dinic(int s,int t)
{
int a[N],cur[N];
int pre[N];
int flow = 0;
int i,u,flag,v,ag,k;
while( BFS(s,t) )
{
for(i=0; i<=t; i++)
{
cur[i] = 0;
a[i] = 0x7fffffff;
}
u = s;
while(1)
{
flag = 0;
for(v=cur[u]; v<=t; v++)
if( mat[u][v] > 0 && lev[u] + 1 == lev[v] )
{
flag = 1;
break;
}
if( flag )
{
cur[u] = v + 1;
pre[v] = u;
a[v] = mat[u][v];
if( a[v] > a[u] )
a[v] = a[u];
u = v;
if( u == t )
{
ag = a[t];
flow += ag;
for(v=t; v!=s; v=pre[v])
{
cur[pre[v]] = v;
mat[pre[v]][v] -= ag;
mat[v][pre[v]] += ag;
a[v] -= ag;
if( mat[pre[v]][v] == 0 )
u = pre[v];
}
}
}
else
if( u != s )
{
lev[u] = 0x7fffffff;
u = pre[u];
}
else break;
}
}
return flow;
}
int main()
{
while ( EOF != scanf("%d", &n) )
{
memset(mat, 0, sizeof(mat));
int i, source, user, nodes;
scanf("%d%d%d", &source, &user, &nodes);
int s, e, t;
for ( i = 0 ; i < nodes ; i++ )
{
scanf("%*[^(](%d,%d)%d", &s, &e, &t);
mat[s][e]=t;
}
for ( i = 0 ; i < source ; i++ )
{
scanf("%*[^(](%d)%d", &e, &t);
mat[n][e]= t;
}
for ( i = 0 ; i < user ; i++ )
{
scanf("%*[^(](%d)%d", &s, &t);
mat[s][n+1]= t;
}
printf("%d\n", Dinic(n, n+1));
}
return 0;
}
看来用40行的代码，换来时间从近600MS到60MS+，近10倍时间的飞跃，还是挺值得的~