2个数,第一个数为最长周期的天数,第二个数为满足最长天数的条件下最短的路程长度(即长度和)。
7 10 1 2 1 1 3 1 2 4 1 3 4 1 4 5 1 4 6 1 2 5 5 3 6 6 5 7 1 6 7 1
2 11
#include<cstdio> #include<cstring> #include<queue> #include<stack> #include<algorithm> using namespace std; #define MAXN 10100 #define INF 0x3f3f3f3f struct node { int u,v,cap,flow,cost,next; }edge[MAXN*50]; int n,m,vis[MAXN],dis[MAXN],pre[MAXN],head[MAXN],cnt1; void init() { memset(head,-1,sizeof(head)); cnt1=0; } void add(int a,int b,int c,int d) { node E={a,b,c,0,d,head[a]}; edge[cnt1]=E; head[a]=cnt1++; node E1={b,a,0,0,-d,head[b]}; edge[cnt1]=E1; head[b]=cnt1++; } bool BFS(int s,int t) { memset(vis,0,sizeof(vis)); memset(dis,INF,sizeof(dis)); memset(pre,-1,sizeof(pre)); vis[s]=1; dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { node E=edge[i]; if(dis[E.v]>dis[u]+E.cost&&E.cap>E.flow) { dis[E.v]=dis[u]+E.cost; pre[E.v]=i; if(!vis[E.v]) { q.push(E.v); vis[E.v]=1; } } } } return pre[t]!=-1; } void mcmf(int s,int t,int &flow,int &cost) { flow=cost=0; while(BFS(s,t)) { int Min=INF; for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]) { node E=edge[i]; Min=min(Min,E.cap-E.flow); } for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]) { edge[i].flow+=Min; edge[i^1].flow-=Min; cost+=edge[i].cost*Min; } flow+=Min; } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { int u,v,w; init(); for(int i=2;i<=n-1;i++) add(i,i+n,1,0);//保证除了1,n其他的只可以用一次 for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); if(u!=1&&u!=n) u+=n; add(u,v,1,w); } int cost,flow; mcmf(1,n,flow,cost); printf("%d %d\n",flow,cost); } return 0; }