\u4ee5\u524d\u6700\u5927\u6d41\u6211\u90fd\u662f\u5199sap\u554a\u3002dinic\u554a\u4e4b\u7c7b\u7684\u590d\u6742\u7b97\u6cd5\u3002\u3002\u611f\u89c9\u5f88\u4e0d\u723d\u3002\u3002\u4f46\u662f\u66b4\u529bdfs\u53c8\u7ecf\u5e38\u8d85\u65f6\uff0c\u800cEK\u7b97\u6cd5\u53cd\u800c\u66f4\u96be\u5199\u3002\u3002\u4e8e\u662f\u6211\u5f88\u7ea0\u7ed3\u3002\u3002
\u4eca\u5929\u6211\u770b\u5230\u4e86\u4e00\u79cd\u5f88\u5e05\u7684\u7b97\u6cd5\u3002\u3002\u5c31\u662f\u6bcf\u6b21\u53ea\u589e\u5e7f\u5bb9\u91cf\u5728K\u4ee5\u4e0a\u7684\u589e\u5e7f\u8def\uff0c\u627e\u4e0d\u5230\u4e86\u5c06k\u96642\u3002\u3002
\u4ee3\u7801\u5f88\u7b80\u5355\uff0c\u65f6\u95f4\u6211\u6d4b\u4e86\u4e00\u4e0b\u5728\u7a00\u758f\u56fe\u4e0a\u662fsap\u76843\u500d\u5de6\u53f3\u3002\u3002
\u54ce\u3002\u3002\u82b1\u4e864000\u4e70\u4e86\u53f0HTC HD2\u3002\u3002\u518d\u662f\u5c71\u5be8\u7684\u6211\u53ea\u80fd\u649e\u6b7b\u4e86\u6655\u3002\u3002
\u6211\u65e0\u804a\u53c8\u8fdb\u884c\u4e86\u4e00\u4e9b\u6d4b\u8bd5\uff0c\u53d1\u73b0\u5728\u8fb9\u6743\u6bd4\u8f83\u53c2\u5dee\u4e0d\u9f50\u7684\u65f6\u5019\u6548\u679c\u8fd8\u662f\u5f88\u597d\u7684\uff0c\u4f46\u5728\u5355\u4f4d\u8fb9\u56fe\u4e0a\u5c31\u9000\u5316\u6210\u66b4\u529bdfs\u4e86\u56e7\u3002\u3002\u4f46\u53ef\u4ee5\u52a0\u4e2a\u9ad8\u5ea6\u51fd\u6570\u4f18\u5316\uff0c\u901f\u5ea6\u5c31\u51e0\u4e4e\u8ddfSAP\u4e00\u6837\u4e86\u3002\u3002\u4e0d\u8fc7\u6ca1\u610f\u4e49\u3002\u3002
Code\uff1a
#include<iostream>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1;
int n,m;
const int V=5000;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}
}*E[V]={0};
int vs,vt,v;
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,c,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int k=0;
bool vis[V]={0};
bool dfs(int no)
{
if(no==vt)return true;
vis[no]=true;
for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c>=k&&dfs(e->t))
{
e->c-=k;e->op->c+=k;return true;
}
return false;
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>m;v=n;int s,t,c;
vs=0;vt=n-1;
while(m–)
{
cin>>s>>t>>c;–s;–t;
AddEdge(s,t,c);
k=c>k?c:k;
}
long long ans=0;
while(k)
{
while(memset(vis,0,sizeof(vis)),dfs(vs))ans+=k;
k>>=1;
}
cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4ee5\u524d\u6700\u5927\u6d41\u6211\u90fd\u662f\u5199sap\u554a\u3002dinic\u554a\u4e4b\u7c7b\u7684\u590d\u6742\u7b97\u6cd5\u3002\u3002\u611f\u89c9\u5f88\u4e0d\u723d\u3002\u3002\u4f46\u662f\u66b4\u529bdfs\u53c8\u7ecf\u5e38\u8d85\u65f6\uff0c\u800cEK\u7b97\u6cd5\u53cd\u800c\u66f4\u96be\u5199\u3002\u3002\u4e8e\u662f\u6211\u5f88\u7ea0\u7ed3\u3002\u3002\u4eca\u5929\u6211\u770b\u5230\u4e86\u4e00\u79cd\u5f88\u5e05\u7684\u7b97\u6cd5\u3002\u3002\u5c31\u662f\u6bcf\u6b21\u53ea\u589e\u5e7f\u5bb9\u91cf\u5728K\u4ee5\u4e0a\u7684\u589e\u5e7f\u8def\uff0c\u627e\u4e0d\u5230\u4e86\u5c06k\u96642\u3002\u3002\u4ee3\u7801\u5f88\u7b80\u5355\uff0c\u65f6\u95f4\u6211\u6d4b\u4e86\u4e00\u4e0b\u5728\u7a00\u758f\u56fe\u4e0a\u662fsap\u76843\u500d\u5de6\u53f3\u3002\u3002\u54ce\u3002\u3002\u82b1\u4e864000\u4e70\u4e86\u53f0HTC HD2\u3002\u3002\u518d\u662f\u5c71\u5be8\u7684\u6211\u53ea\u80fd\u649e\u6b7b\u4e86\u6655\u3002\u3002\u6211\u65e0\u804a\u53c8\u8fdb\u884c\u4e86\u4e00\u4e9b\u6d4b\u8bd5\uff0c\u53d1\u73b0\u5728\u8fb9\u6743\u6bd4\u8f83\u53c2\u5dee\u4e0d\u9f50\u7684\u65f6\u5019\u6548\u679c\u8fd8\u662f\u5f88\u597d\u7684\uff0c\u4f46\u5728\u5355\u4f4d\u8fb9\u56fe\u4e0a\u5c31\u9000\u5316\u6210\u66b4\u529bdfs\u4e86\u56e7\u3002\u3002\u4f46\u53ef\u4ee5\u52a0\u4e2a\u9ad8\u5ea6\u51fd\u6570\u4f18\u5316\uff0c\u901f\u5ea6\u5c31\u51e0\u4e4e\u8ddfSAP\u4e00\u6837\u4e86\u3002\u3002\u4e0d\u8fc7\u6ca1\u610f\u4e49\u3002\u3002Code\uff1a#include<iostream>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1;int n,m;const int V=5000;struct Edge{ int t,c; Edge*next,*op; Edge(int _t,int _c,Edge*_n):t(_t),c(_c),next(_n){}}*E[V]={0};int vs,vt,v;void AddEdge(int s,int t,int c){ E[s]=new Edge(t,c,E[s]); E[t]=new Edge(s,c,E[t]); E[s]->op=E[t];E[t]->op=E[s];}int k=0;bool vis[V]={0};bool dfs(int no){ if(no==vt)return true; vis[no]=true; for(Edge*e=E[no];e;e=e->next)if(!vis[e->t]&&e->c>=k&&dfs(e->t)) { e->c-=k;e->op->c+=k;return true; } return false;}int main(){ \/\/freopen("in","r",stdin); cin>>n>>m;v=n;int s,t,c; vs=0;vt=n-1; while(m–) { cin>>s>>t>>c;–s;–t; AddEdge(s,t,c); k=c>k?c:k; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/224"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=224"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/224\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}