| 记录编号 |
119060 |
评测结果 |
AAAAAAAAAAAA |
| 题目名称 |
追查坏牛奶 |
最终得分 |
100 |
| 用户昵称 |
 HouJikan |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.028 s |
| 提交时间 |
2014-09-10 21:43:56 |
内存使用 |
0.29 MiB |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint;
const int INF=0x7fffffff;
//==============struct declaration==============
struct adj
{
int from,to,cap;
LL flow;
adj(int from=0,int to=0,int cap=0,LL flow=0):from(from),to(to),cap(cap),flow(flow){}
};
//==============var declaration=================
const int MAXN=40;
int n,m,tot=0;
int p[MAXN],cur[MAXN],gap[MAXN],d[MAXN];
vector <int> G[MAXN];
vector <adj> Edge;
//==============function declaration============
void ISAP();
LL argument();
void bfs();
void cut();
//==============main code=======================
int main()
{
string FileName="milk6";//程序名
string FloderName="COGS";//文件夹名
freopen((FileName+".in").c_str(),"r",stdin);
freopen((FileName+".out").c_str(),"w",stdout);
ios::sync_with_stdio(false);
#ifdef DEBUG
system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
clock_t Start_Time=clock();
#endif
scanf("%d%d",&n,&m);
For(i,1,m)
{
int s,e;
LL cap;
scanf("%d%d%lld",&s,&e,&cap);
G[s].push_back(tot++);
Edge.push_back(adj(s,e,cap,0));
G[e].push_back(tot++);
Edge.push_back(adj(e,s,0,0));
}
ISAP();
for(int i=0;i<=m*2-1;i+=2)
{
if (Edge[i].cap==Edge[i].flow)
{
Edge[i].cap=1;
Edge[i].flow=0;
}
Edge[i+1].flow=0;
}
ISAP();
cut();
#ifdef DEBUG
clock_t End_Time=clock();
cout<<endl<<endl<<"Time Used: "<<double(End_Time-Start_Time)/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}
//================fuction code====================
void ISAP()
{
memset(d,-1,sizeof(d));
memset(cur,0,sizeof(cur));
memset(gap,0,sizeof(gap));
bfs();
LL sumflow=0;
int x=1;
while (d[1]<n)
{
if (x==n)
{
sumflow+=argument();
x=1;
}
int siz=G[x].size()-1;
bool suc=false;
For(i,cur[x],siz)
{
adj &e=Edge[G[x][i]];
if (d[e.to]==d[x]-1&&e.cap>e.flow)
{
suc=true;
cur[x]=i;
p[e.to]=G[x][i];
x=e.to;
break;
}
}
if (!suc)
{
int mind=n-1;
For(i,0,siz)
{
adj &e=Edge[G[x][i]];
if (e.cap>e.flow&&d[e.to]<mind)
mind=d[e.to];
}
gap[d[x]]--;
if (gap[d[x]]==0)
break;
d[x]=mind+1;
gap[d[x]]++;
cur[x]=0;
if (x!=1)
x=Edge[p[x]].from;
}
}
printf("%lld ",sumflow);
}
void bfs()
{
queue <int> Q;
Q.push(n);
d[n]=0;
while (!Q.empty())
{
int now=Q.front();Q.pop();
int siz=G[now].size()-1;
gap[d[now]]++;
For(i,0,siz)
{
adj &e=Edge[G[now][i]];
if (d[e.to]==-1)
{
d[e.to]=d[now]+1;
Q.push(e.to);
}
}
}
}
LL argument()
{
LL flow=INF;
int x=n;
while (x!=1)
{
adj &e=Edge[p[x]];
flow=min(flow,e.cap-e.flow);
x=e.from;
}
x=n;
while (x!=1)
{
Edge[p[x]].flow+=flow;
Edge[p[x]^1].flow-=flow;
x=Edge[p[x]].from;
}
return flow;
}
void cut()
{
int scnt=0,ecnt=0,smin=INF,emin=INF;
bool scut[1010*2],ecut[1010*2];
bool color[1010*2];
memset(scut,false,sizeof(scut));
memset(color,false,sizeof(color));
queue <int> Q;
Q.push(1);
color[1]=true;
while (!Q.empty())
{
int now=Q.front();Q.pop();
int siz=G[now].size()-1;
For(i,0,siz)
{
adj &e=Edge[G[now][i]];
if (e.cap>e.flow&&!color[e.to])
{
Q.push(e.to);
color[e.to]=true;
}
}
}
For(i,1,MAXN)
{
if (!color[i]) continue;
int siz=G[i].size()-1;
For(j,0,siz)
{
adj &e=Edge[G[i][j]];
if (!color[e.to]&&e.cap==e.flow&&e.cap!=0)
{
scut[G[i][j]]=true;
smin=min(smin,G[i][j]);
}
}
}
For(i,0,m*2+1)
if (scut[i])
scnt++;
//从源点查找割边
memset(ecut,false,sizeof(scut));
memset(color,false,sizeof(color));
Q.push(n);
color[n]=true;
while (!Q.empty())
{
int now=Q.front();Q.pop();
int siz=G[now].size()-1;
For(i,0,siz)
{
adj &e=Edge[G[now][i]^1];
if (e.cap!=0&&e.cap>e.flow&&!color[e.from])
{
Q.push(e.from);
color[e.from]=true;
}
}
}
For(i,1,MAXN)
{
if (!color[i]) continue;
int siz=G[i].size()-1;
For(j,0,siz)
{
adj &e=Edge[G[i][j]^1];
if (!color[e.from]&&e.cap==e.flow&&e.cap!=0)
{
ecut[G[i][j]^1]=true;
emin=min(emin,G[i][j]^1);
}
}
}
For(i,0,m*2+1)
if (ecut[i])
ecnt++;
if (scnt<ecnt||(scnt==ecnt&&smin<=emin))
{
For(i,0,m*2-1)
if (scut[i])
printf("%d",i/2+1);
}
else
{
For(i,0,m*2-1)
if (ecut[i])
printf("%d",i/2+1);
}
}